{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,2]],"date-time":"2026-06-02T04:35:46Z","timestamp":1780374946331,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":77,"publisher":"ACM","license":[{"start":{"date-parts":[[2019,6,23]],"date-time":"2019-06-23T00:00:00Z","timestamp":1561248000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1526799"],"award-info":[{"award-number":["CCF-1526799"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2019,6,23]]},"DOI":"10.1145\/3313276.3316406","type":"proceedings-article","created":{"date-parts":[[2019,6,20]],"date-time":"2019-06-20T12:19:08Z","timestamp":1561033148000},"page":"78-89","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":18,"title":["Parallelizing greedy for submodular set function maximization in matroids and beyond"],"prefix":"10.1145","author":[{"given":"Chandra","family":"Chekuri","sequence":"first","affiliation":[{"name":"University of Illinois at Urbana-Champaign, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kent","family":"Quanrud","sequence":"additional","affiliation":[{"name":"University of Illinois at Urbana-Champaign, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2019,6,23]]},"reference":[{"key":"e_1_3_2_1_1_1","unstructured":"Ashwinkumar Badanidiyuru Baharan Mirzasoleiman Amin Karbasi and Andreas Krause. 2014.  Ashwinkumar Badanidiyuru Baharan Mirzasoleiman Amin Karbasi and Andreas Krause. 2014."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623637"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634184"},{"key":"e_1_3_2_1_4_1","volume-title":"Non-monotone Submodular Maximization in Exponentially Fewer Iterations. CoRR abs\/1807.11462","author":"Balkanski Eric","year":"2018","unstructured":"Eric Balkanski , Adam Breuer , and Yaron Singer . 2018. Non-monotone Submodular Maximization in Exponentially Fewer Iterations. CoRR abs\/1807.11462 ( 2018 ). http:\/\/arxiv.org\/abs\/1807.11462 To appear in NIPS , 2018. Eric Balkanski, Adam Breuer, and Yaron Singer. 2018. Non-monotone Submodular Maximization in Exponentially Fewer Iterations. CoRR abs\/1807.11462 (2018). http:\/\/arxiv.org\/abs\/1807.11462 To appear in NIPS, 2018."},{"key":"e_1_3_2_1_5_1","unstructured":"Eric Balkanski Aviad Rubinstein and Yaron Singer. 2017.  Eric Balkanski Aviad Rubinstein and Yaron Singer. 2017."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055406"},{"key":"e_1_3_2_1_7_1","unstructured":"Eric Balkanski Aviad Rubinstein and Yaron Singer. 2018.  Eric Balkanski Aviad Rubinstein and Yaron Singer. 2018."},{"key":"e_1_3_2_1_8_1","volume-title":"CoRR abs\/1811.03093 (Nov","author":"Submodular Maximization An Optimal","year":"2018","unstructured":"An Optimal Approximation for Submodular Maximization under a Matroid Constraint in the Adaptive Complexity Model . CoRR abs\/1811.03093 (Nov . 2018 ). https: \/\/arxiv.org\/abs\/1811.03093 An Optimal Approximation for Submodular Maximization under a Matroid Constraint in the Adaptive Complexity Model. CoRR abs\/1811.03093 (Nov. 2018). https: \/\/arxiv.org\/abs\/1811.03093"},{"key":"e_1_3_2_1_9_1","unstructured":"Eric Balkanski Aviad Rubinstein and Yaron Singer. 2019.  Eric Balkanski Aviad Rubinstein and Yaron Singer. 2019."},{"key":"e_1_3_2_1_10_1","volume-title":"Loss in Approximation. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019","author":"Parallel Running An Exponential","year":"2019","unstructured":"An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019 , San Diego, California, USA , January 6-9, 2019 . An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019."},{"key":"e_1_3_2_1_11_1","unstructured":"283\u2013302.  283\u2013302."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188752"},{"key":"e_1_3_2_1_13_1","unstructured":"1138\u20131151.  1138\u20131151."},{"key":"e_1_3_2_1_14_1","volume-title":"Proceedings of the 32nd International Conference on Machine Learning, ICML 2015","author":"da Ponte Barbosa Rafael","year":"2015","unstructured":"Rafael da Ponte Barbosa , Alina Ene , Huy L. Nguyen , and Justin Ward . 2015 . The Power of Randomization: Distributed Submodular Maximization on Massive Datasets . In Proceedings of the 32nd International Conference on Machine Learning, ICML 2015 , Lille, France , 6-11 July 2015. 1236\u20131244. Rafael da Ponte Barbosa, Alina Ene, Huy L. Nguyen, and Justin Ward. 2015. The Power of Randomization: Distributed Submodular Maximization on Massive Datasets. In Proceedings of the 32nd International Conference on Machine Learning, ICML 2015, Lille, France, 6-11 July 2015. 1236\u20131244."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.74"},{"key":"e_1_3_2_1_16_1","unstructured":"Guy E. Blelloch Richard Peng and Kanat Tangwongsan. 2011.  Guy E. Blelloch Richard Peng and Kanat Tangwongsan. 2011."},{"key":"e_1_3_2_1_17_1","volume-title":"SPAA 2011: Proceedings of the 23rd Annual ACM Symposium on Parallelism in Algorithms and Architectures","year":"2011","unstructured":"Linear-work greedy parallel approximate set cover and variants. In SPAA 2011: Proceedings of the 23rd Annual ACM Symposium on Parallelism in Algorithms and Architectures , San Jose, CA, USA , June 4-6, 2011 (Co-located with FCRC 2011), Rajmohan Rajaraman and Friedhelm Meyer auf der Heide (Eds.). ACM , 23\u201332. Linear-work greedy parallel approximate set cover and variants. In SPAA 2011: Proceedings of the 23rd Annual ACM Symposium on Parallelism in Algorithms and Architectures, San Jose, CA, USA, June 4-6, 2011 (Co-located with FCRC 2011), Rajmohan Rajaraman and Friedhelm Meyer auf der Heide (Eds.). ACM, 23\u201332."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(82)90766-5"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1017\/S000497270004140X"},{"key":"e_1_3_2_1_20_1","unstructured":"Niv Buchbinder and Moran Feldman. 2016.  Niv Buchbinder and Moran Feldman. 2016."},{"key":"e_1_3_2_1_21_1","volume-title":"CoRR abs\/1611.03253","author":"Technique Constrained Submodular","year":"2016","unstructured":"Constrained Submodular Maximization via a Non-symmetric Technique . CoRR abs\/1611.03253 ( 2016 ). Constrained Submodular Maximization via a Non-symmetric Technique. CoRR abs\/1611.03253 (2016)."},{"key":"e_1_3_2_1_22_1","unstructured":"arXiv: 1611.03253 http:\/\/arxiv.org\/abs\/1611.03253  arXiv: 1611.03253 http:\/\/arxiv.org\/abs\/1611.03253"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973730.80"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2016.0809"},{"key":"e_1_3_2_1_25_1","volume-title":"June 23\u201326","author":"Buchbinder Niv","year":"2019","unstructured":"Niv Buchbinder , Moran Feldman , Joseph Seffi , and Roy Schwartz . 2015. A tight linear time (1\/2)-approximation for unconstrained submodular maximization. STOC \u201919 , June 23\u201326 , 2019 , Phoenix, AZ , USA Chandra Chekuri and Kent Quanrud SIAM J. Comput . 44, 5 (2015), 1384\u20131402. Niv Buchbinder, Moran Feldman, Joseph Seffi, and Roy Schwartz. 2015. A tight linear time (1\/2)-approximation for unconstrained submodular maximization. STOC \u201919, June 23\u201326, 2019, Phoenix, AZ, USA Chandra Chekuri and Kent Quanrud SIAM J. Comput. 44, 5 (2015), 1384\u20131402."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/080733991"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-015-0900-7"},{"key":"e_1_3_2_1_28_1","unstructured":"T.-H. Hubert Chan Zhiyi Huang Shaofeng H.-C. Jiang Ning Kang and Zhihao Gavin Tang. 2018.  T.-H. Hubert Chan Zhiyi Huang Shaofeng H.-C. Jiang Ning Kang and Zhihao Gavin Tang. 2018."},{"key":"e_1_3_2_1_29_1","volume-title":"Algorithms 14, 4","author":"Free Disposal Online Submodular","year":"2018","unstructured":"Online Submodular Maximization with Free Disposal . ACM Trans . Algorithms 14, 4 ( 2018 ), 56:1\u201356:29. Preliminary version in SODA , 2017. Online Submodular Maximization with Free Disposal. ACM Trans. Algorithms 14, 4 (2018), 56:1\u201356:29. Preliminary version in SODA, 2017."},{"key":"e_1_3_2_1_30_1","volume-title":"42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I. 318\u2013330","author":"Chekuri Chandra","year":"2015","unstructured":"Chandra Chekuri , Shalmoli Gupta , and Kent Quanrud . 2015 . Streaming Algorithms for Submodular Function Maximization. In Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I. 318\u2013330 . Chandra Chekuri, Shalmoli Gupta, and Kent Quanrud. 2015. Streaming Algorithms for Submodular Function Maximization. In Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I. 318\u2013330."},{"key":"e_1_3_2_1_31_1","volume-title":"Parallelizing greedy for submodular set function maximization in matroids and beyond. CoRR abs\/1811.12568","author":"Chekuri Chandra","year":"2018","unstructured":"Chandra Chekuri and Kent Quanrud . 2018. Parallelizing greedy for submodular set function maximization in matroids and beyond. CoRR abs\/1811.12568 ( 2018 ). Chandra Chekuri and Kent Quanrud. 2018. Parallelizing greedy for submodular set function maximization in matroids and beyond. CoRR abs\/1811.12568 (2018)."},{"key":"e_1_3_2_1_32_1","unstructured":"arXiv: 1811.12568 http:\/\/arxiv.org\/abs\/1811.12568  arXiv: 1811.12568 http:\/\/arxiv.org\/abs\/1811.12568"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.20"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.60"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/110839655"},{"key":"e_1_3_2_1_36_1","volume-title":"Fundamentals of Computation Theory, FCT \u201985","author":"Chistov Alexander L.","year":"1985","unstructured":"Alexander L. Chistov . 1985. Fast parallel calculation of the rank of matrices over a field of arbitrary characteristic . In Fundamentals of Computation Theory, FCT \u201985 , Cottbus , GDR , September 9-13, 1985 . 63\u201369. Alexander L. Chistov. 1985. Fast parallel calculation of the rank of matrices over a field of arbitrary characteristic. In Fundamentals of Computation Theory, FCT \u201985, Cottbus, GDR, September 9-13, 1985. 63\u201369."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.34"},{"key":"e_1_3_2_1_38_1","volume-title":"Nguyen","author":"Ene Alina","year":"2017","unstructured":"Alina Ene and Huy L . Nguyen . 2017 . A Nearly-linear Time Algorithm for Submodular Maximization with a Knapsack Constraint. CoRR abs\/1709.09767 (2017). http:\/\/arxiv.org\/abs\/1709.09767 Alina Ene and Huy L. Nguyen. 2017. A Nearly-linear Time Algorithm for Submodular Maximization with a Knapsack Constraint. CoRR abs\/1709.09767 (2017). http:\/\/arxiv.org\/abs\/1709.09767"},{"key":"e_1_3_2_1_39_1","volume-title":"Nguyen","author":"Ene Alina","year":"2019","unstructured":"Alina Ene and Huy L . Nguyen . 2019 . Alina Ene and Huy L. Nguyen. 2019."},{"key":"e_1_3_2_1_40_1","volume-title":"Maximization with Nearlyoptimal Approximation and Adaptivity in Nearly-linear Time. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019","author":"Submodular","year":"2019","unstructured":"Submodular Maximization with Nearlyoptimal Approximation and Adaptivity in Nearly-linear Time. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019 , San Diego, California, USA , January 6-9, 2019 . 274\u2013282. Submodular Maximization with Nearlyoptimal Approximation and Adaptivity in Nearly-linear Time. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019. 274\u2013282."},{"key":"e_1_3_2_1_41_1","volume-title":"Submodular Maximization with Matroid and Packing Constraints in Parallel. CoRR abs\/1808.09987v2 (Nov","author":"Ene Alina","year":"2018","unstructured":"Alina Ene , Huy L. Nguyen , and Adrian Vladu . 2018. Submodular Maximization with Matroid and Packing Constraints in Parallel. CoRR abs\/1808.09987v2 (Nov . 2018 ). http:\/\/arxiv.org\/abs\/1808.09987v2 Alina Ene, Huy L. Nguyen, and Adrian Vladu. 2018. Submodular Maximization with Matroid and Packing Constraints in Parallel. CoRR abs\/1808.09987v2 (Nov. 2018). http:\/\/arxiv.org\/abs\/1808.09987v2"},{"key":"e_1_3_2_1_42_1","volume-title":"Submodular Maximization with Packing Constraints in Parallel. CoRR abs\/1808.09987v1 (Aug","author":"Ene Alina","year":"2018","unstructured":"Alina Ene , Huy L. Nguyen , and Adrian Vladu . 2018. Submodular Maximization with Packing Constraints in Parallel. CoRR abs\/1808.09987v1 (Aug . 2018 ). http: \/\/arxiv.org\/abs\/1808.09987v1 Alina Ene, Huy L. Nguyen, and Adrian Vladu. 2018. Submodular Maximization with Packing Constraints in Parallel. CoRR abs\/1808.09987v1 (Aug. 2018). http: \/\/arxiv.org\/abs\/1808.09987v1"},{"key":"e_1_3_2_1_43_1","volume-title":"Nonmonotone Submodular Maximization with Nearly Optimal Adaptivity Complexity. CoRR abs\/1808.06932","author":"Fahrbach Matthew","year":"2018","unstructured":"Matthew Fahrbach , Vahab S. Mirrokni , and Morteza Zadimoghaddam . 2018. Nonmonotone Submodular Maximization with Nearly Optimal Adaptivity Complexity. CoRR abs\/1808.06932 ( 2018 ). arXiv: 1808.06932 http:\/\/arxiv.org\/abs\/1808.06932 Matthew Fahrbach, Vahab S. Mirrokni, and Morteza Zadimoghaddam. 2018. Nonmonotone Submodular Maximization with Nearly Optimal Adaptivity Complexity. CoRR abs\/1808.06932 (2018). arXiv: 1808.06932 http:\/\/arxiv.org\/abs\/1808.06932"},{"key":"e_1_3_2_1_44_1","unstructured":"Matthew Fahrbach Vahab S. Mirrokni and Morteza Zadimoghaddam. 2018.  Matthew Fahrbach Vahab S. Mirrokni and Morteza Zadimoghaddam. 2018."},{"key":"e_1_3_2_1_45_1","volume-title":"Adaptivity and Query Complexity. CoRR abs\/1807.07889","author":"Optimal Approximation Submodular Maximization","year":"2018","unstructured":"Submodular Maximization with Optimal Approximation , Adaptivity and Query Complexity. CoRR abs\/1807.07889 ( 2018 ). arXiv: 1807.07889 http:\/\/arxiv.org\/abs\/ 1807.07889 Submodular Maximization with Optimal Approximation, Adaptivity and Query Complexity. CoRR abs\/1807.07889 (2018). arXiv: 1807.07889 http:\/\/arxiv.org\/abs\/ 1807.07889"},{"key":"e_1_3_2_1_46_1","unstructured":"U. Feige. 1998.  U. Feige. 1998."},{"key":"e_1_3_2_1_47_1","volume-title":"Preliminary version in STOC","author":"Approximating Set Cover A Threshold","year":"1996","unstructured":"A Threshold of ln n for Approximating Set Cover . 45, 4 ( July 1998), 634\u2013652. Preliminary version in STOC , 1996 . A Threshold of ln n for Approximating Set Cover. 45, 4 (July 1998), 634\u2013652. Preliminary version in STOC, 1996."},{"key":"e_1_3_2_1_48_1","volume-title":"Proceedings of the 30th Conference on Learning Theory, COLT 2017","author":"Feldman Moran","year":"2017","unstructured":"Moran Feldman , Christopher Harshaw , and Amin Karbasi . 2017 . Greed Is Good: Near-Optimal Submodular Maximization via Greedy Optimization . In Proceedings of the 30th Conference on Learning Theory, COLT 2017 , Amsterdam, The Netherlands , 7-10 July 2017. 758\u2013784. Moran Feldman, Christopher Harshaw, and Amin Karbasi. 2017. Greed Is Good: Near-Optimal Submodular Maximization via Greedy Optimization. In Proceedings of the 30th Conference on Learning Theory, COLT 2017, Amsterdam, The Netherlands, 7-10 July 2017. 758\u2013784."},{"key":"e_1_3_2_1_49_1","unstructured":"Moran Feldman Amin Karbasi and Ehsan Kazemi. 2018.  Moran Feldman Amin Karbasi and Ehsan Kazemi. 2018."},{"key":"e_1_3_2_1_50_1","volume-title":"Get More: Streaming Submodular Maximization with Subsampling. CoRR abs\/1802.07098","author":"Less Do","year":"2018","unstructured":"Do Less , Get More: Streaming Submodular Maximization with Subsampling. CoRR abs\/1802.07098 ( 2018 ). arXiv: 1802.07098 http:\/\/arxiv.org\/abs\/1802.07098 Do Less, Get More: Streaming Submodular Maximization with Subsampling. CoRR abs\/1802.07098 (2018). arXiv: 1802.07098 http:\/\/arxiv.org\/abs\/1802.07098"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.46"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1137\/130920277"},{"key":"e_1_3_2_1_53_1","unstructured":"Marshall L Fisher George L Nemhauser and Laurence A Wolsey. 1978.  Marshall L Fisher George L Nemhauser and Laurence A Wolsey. 1978."},{"key":"e_1_3_2_1_54_1","volume-title":"Polyhedral combinatorics","author":"An","unstructured":"An analysis of approximations for maximizing submodular set functions\u2014II. In Polyhedral combinatorics . Springer , 73\u201387. An analysis of approximations for maximizing submodular set functions\u2014II. In Polyhedral combinatorics. Springer, 73\u201387."},{"key":"e_1_3_2_1_55_1","volume-title":"APPROX\/RANDOM 2017","author":"Huang Chien-Chung","year":"2017","unstructured":"Chien-Chung Huang , Naonori Kakimura , and Yuichi Yoshida . 2017 . Streaming Algorithms for Maximizing Monotone Submodular Functions under a Knapsack Constraint. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques , APPROX\/RANDOM 2017 , August 16-18, 2017, Berkeley, CA, USA. 11:1\u201311:14. Chien-Chung Huang, Naonori Kakimura, and Yuichi Yoshida. 2017. Streaming Algorithms for Maximizing Monotone Submodular Functions under a Knapsack Constraint. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM 2017, August 16-18, 2017, Berkeley, CA, USA. 11:1\u201311:14."},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(80)90042-3"},{"key":"e_1_3_2_1_57_1","unstructured":"Richard M. Karp Eli Upfal and Avi Wigderson. 1986.  Richard M. Karp Eli Upfal and Avi Wigderson. 1986."},{"key":"e_1_3_2_1_58_1","volume-title":"35\u201348","author":"Constructing","year":"1986","unstructured":"Constructing a perfect matching is in random NC. Combinatorica 6, 1 ( 1986 ), 35\u201348 . Constructing a perfect matching is in random NC. Combinatorica 6, 1 (1986), 35\u201348."},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.5555\/49981.49986"},{"key":"e_1_3_2_1_60_1","unstructured":"Ravi Kumar Benjamin Moseley Sergei Vassilvitskii and Andrea Vattani. 2015.  Ravi Kumar Benjamin Moseley Sergei Vassilvitskii and Andrea Vattani. 2015."},{"key":"e_1_3_2_1_61_1","volume-title":"14:1\u2013 14:22. Preliminary version in SPAA","author":"MapReduce Fast Greedy","year":"2015","unstructured":"Fast Greedy Algorithms in MapReduce and Streaming. TOPC 2, 3 ( 2015 ), 14:1\u2013 14:22. Preliminary version in SPAA , 2013. Fast Greedy Algorithms in MapReduce and Streaming. TOPC 2, 3 (2015), 14:1\u2013 14:22. Preliminary version in SPAA, 2013."},{"key":"e_1_3_2_1_62_1","volume-title":"Submodular optimization in the MapReduce model. CoRR abs\/1810.01489","author":"Liu Paul","year":"2018","unstructured":"Paul Liu and Jan Vondr\u00e1k . 2018. Submodular optimization in the MapReduce model. CoRR abs\/1810.01489 ( 2018 ). http:\/\/arxiv.org\/abs\/1810.01489 To appear in SOSA 2019. Paul Liu and Jan Vondr\u00e1k. 2018. Submodular optimization in the MapReduce model. CoRR abs\/1810.01489 (2018). http:\/\/arxiv.org\/abs\/1810.01489 To appear in SOSA 2019."},{"key":"e_1_3_2_1_63_1","volume-title":"Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015","author":"Vahab","year":"2015","unstructured":"Vahab S. Mirrokni and Morteza Zadimoghaddam. 2015. Randomized Composable Core-sets for Distributed Submodular Maximization . In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015 , Portland, OR, USA , June 14-17, 2015 . 153\u2013162. Vahab S. Mirrokni and Morteza Zadimoghaddam. 2015. Randomized Composable Core-sets for Distributed Submodular Maximization. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015. 153\u2013162."},{"key":"e_1_3_2_1_64_1","unstructured":"Baharan Mirzasoleiman Ashwinkumar Badanidiyuru and Amin Karbasi. 2016.  Baharan Mirzasoleiman Ashwinkumar Badanidiyuru and Amin Karbasi. 2016."},{"key":"e_1_3_2_1_65_1","volume-title":"Constrained Submodular Maximization: Personalized Data Summarization. In Proceedings of the 33nd International Conference on Machine Learning, ICML 2016","author":"Fast","year":"2016","unstructured":"Fast Constrained Submodular Maximization: Personalized Data Summarization. In Proceedings of the 33nd International Conference on Machine Learning, ICML 2016 , New York City, NY, USA , June 19-24, 2016 . 1358\u20131367. Fast Constrained Submodular Maximization: Personalized Data Summarization. In Proceedings of the 33nd International Conference on Machine Learning, ICML 2016, New York City, NY, USA, June 19-24, 2016. 1358\u20131367."},{"key":"e_1_3_2_1_66_1","unstructured":"Baharan Mirzasoleiman Ashwinkumar Badanidiyuru Amin Karbasi Jan Vondr\u00e1k and Andreas Krause. 2015.  Baharan Mirzasoleiman Ashwinkumar Badanidiyuru Amin Karbasi Jan Vondr\u00e1k and Andreas Krause. 2015."},{"key":"e_1_3_2_1_67_1","volume-title":"Than Lazy Greedy. In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence","author":"Lazier","year":"2015","unstructured":"Lazier Than Lazy Greedy. In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence , January 25-30, 2015 , Austin, Texas, USA. 1812\u20131818. Lazier Than Lazy Greedy. In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, January 25-30, 2015, Austin, Texas, USA. 1812\u20131818."},{"key":"e_1_3_2_1_68_1","volume-title":"Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI-18)","author":"Mirzasoleiman Baharan","year":"2018","unstructured":"Baharan Mirzasoleiman , Stefanie Jegelka , and Andreas Krause . 2018 . Streaming Non-Monotone Submodular Maximization: Personalized Video Summarization on the Fly . In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI-18) , the 30th innovative Applications of Artificial Intelligence (IAAI-18), and the 8th AAAI Symposium on Educational Advances in Artificial Intelligence (EAAI-18), New Orleans, Louisiana, USA , February 2-7, 2018. 1379\u2013 1386. Baharan Mirzasoleiman, Stefanie Jegelka, and Andreas Krause. 2018. Streaming Non-Monotone Submodular Maximization: Personalized Video Summarization on the Fly. In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI-18), the 30th innovative Applications of Artificial Intelligence (IAAI-18), and the 8th AAAI Symposium on Educational Advances in Artificial Intelligence (EAAI-18), New Orleans, Louisiana, USA, February 2-7, 2018. 1379\u2013 1386."},{"key":"e_1_3_2_1_69_1","unstructured":"Baharan Mirzasoleiman Amin Karbasi Rik Sarkar and Andreas Krause. 2016.  Baharan Mirzasoleiman Amin Karbasi Rik Sarkar and Andreas Krause. 2016."},{"key":"e_1_3_2_1_70_1","volume-title":"Journal of Machine Learning Research 17","author":"Maximization Distributed Submodular","year":"2016","unstructured":"Distributed Submodular Maximization . Journal of Machine Learning Research 17 ( 2016 ), 238:1\u2013238:44. Preliminary version in NIPS , 2013. Distributed Submodular Maximization. Journal of Machine Learning Research 17 (2016), 238:1\u2013238:44. Preliminary version in NIPS, 2013."},{"key":"e_1_3_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579205"},{"key":"e_1_3_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539791195245"},{"key":"e_1_3_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01588971"},{"key":"e_1_3_2_1_74_1","unstructured":"Ashkan Norouzi-Fard Jakub Tarnawski Slobodan Mitrovic Amir Zandieh Aidasadat Mousavifar and Ola Svensson. 2018.  Ashkan Norouzi-Fard Jakub Tarnawski Slobodan Mitrovic Amir Zandieh Aidasadat Mousavifar and Ola Svensson. 2018."},{"key":"e_1_3_2_1_75_1","volume-title":"Submodular Maximization on Massive Data Streams. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsm\u00e4ssan","author":"Beyond","year":"2018","unstructured":"Beyond 1 \/2-Approximation for Submodular Maximization on Massive Data Streams. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsm\u00e4ssan , Stockholm, Sweden , July 10-15, 2018 . 3826\u20133835. Beyond 1 \/2-Approximation for Submodular Maximization on Massive Data Streams. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsm\u00e4ssan, Stockholm, Sweden, July 10-15, 2018. 3826\u20133835."},{"key":"e_1_3_2_1_76_1","unstructured":"Alexander Schrijver. 2003.  Alexander Schrijver. 2003."},{"key":"e_1_3_2_1_77_1","volume-title":"polyhedra and efficiency","author":"Combinatorial","unstructured":"Combinatorial optimization : polyhedra and efficiency . Vol. 24 . Springer Science & amp; Business Media. Combinatorial optimization: polyhedra and efficiency. Vol. 24. Springer Science & Business Media."}],"event":{"name":"STOC '19: 51st Annual ACM SIGACT Symposium on the Theory of Computing","location":"Phoenix AZ USA","acronym":"STOC '19","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313276.3316406","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3313276.3316406","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3313276.3316406","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:54:33Z","timestamp":1750204473000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313276.3316406"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,23]]},"references-count":77,"alternative-id":["10.1145\/3313276.3316406","10.1145\/3313276"],"URL":"https:\/\/doi.org\/10.1145\/3313276.3316406","relation":{},"subject":[],"published":{"date-parts":[[2019,6,23]]},"assertion":[{"value":"2019-06-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}