{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T11:21:18Z","timestamp":1770895278530,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":39,"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-1750333,CCF-1718342,CCF-1750716"],"award-info":[{"award-number":["CCF-1750333,CCF-1718342,CCF-1750716"]}],"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.3316389","type":"proceedings-article","created":{"date-parts":[[2019,6,20]],"date-time":"2019-06-20T12:19:08Z","timestamp":1561033148000},"page":"90-101","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["Submodular maximization with matroid and packing constraints in parallel"],"prefix":"10.1145","author":[{"given":"Alina","family":"Ene","sequence":"first","affiliation":[{"name":"Boston University, USA"}]},{"given":"Huy L.","family":"Nguy\u1ec5n","sequence":"additional","affiliation":[{"name":"Northeastern University, USA"}]},{"given":"Adrian","family":"Vladu","sequence":"additional","affiliation":[{"name":"Boston University, USA"}]}],"member":"320","published-online":{"date-parts":[[2019,6,23]]},"reference":[{"key":"e_1_3_2_1_1_1","unstructured":"Zeyuan Allen-Zhu and Lorenzo Orecchia. 2015.  Zeyuan Allen-Zhu and Lorenzo Orecchia. 2015."},{"key":"e_1_3_2_1_2_1","volume-title":"ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 1439\u20131456","author":"Using"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-018-1248-6"},{"key":"e_1_3_2_1_4_1","unstructured":"Eric Balkanski Adam Breuer and Yaron Singer. 2018. Non-monotone Submodular Maximization in Exponentially Fewer Iterations. arXiv preprint arXiv:1807.11462 (2018).  Eric Balkanski Adam Breuer and Yaron Singer. 2018. Non-monotone Submodular Maximization in Exponentially Fewer Iterations. arXiv preprint arXiv:1807.11462 (2018)."},{"key":"e_1_3_2_1_5_1","unstructured":"Eric Balkanski Aviad Rubinstein and Yaron Singer. 2018.  Eric Balkanski Aviad Rubinstein and Yaron Singer. 2018."},{"key":"e_1_3_2_1_6_1","unstructured":"An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation. CoRR abs\/1804.06355 (2018).  An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation. CoRR abs\/1804.06355 (2018)."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188752"},{"key":"e_1_3_2_1_8_1","volume-title":"The Power of Randomization: Distributed Submodular Maximization on Massive Datasets. In International Conference on Machine Learning (ICML).","author":"Barbosa Rafael D.P.","year":"2015"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"crossref","unstructured":"Rafael da Ponte Barbosa Alina Ene Huy L Nguyen and Justin Ward. 2016. A new framework for distributed submodular maximization. In IEEE Foundations of Computer Science (FOCS). 645\u2013654.  Rafael da Ponte Barbosa Alina Ene Huy L Nguyen and Justin Ward. 2016. A new framework for distributed submodular maximization. In IEEE Foundations of Computer Science (FOCS). 645\u2013654.","DOI":"10.1109\/FOCS.2016.74"},{"key":"e_1_3_2_1_10_1","unstructured":"An Bian Joachim M Buhmann and Andreas Krause. 2018.  An Bian Joachim M Buhmann and Andreas Krause. 2018."},{"key":"e_1_3_2_1_11_1","unstructured":"Optimal DRSubmodular Maximization and Applications to Provable Mean Field Inference. arXiv preprint arXiv:1805.07482 (2018).  Optimal DRSubmodular Maximization and Applications to Provable Mean Field Inference. arXiv preprint arXiv:1805.07482 (2018)."},{"key":"e_1_3_2_1_12_1","unstructured":"An Bian Kfir Levy Andreas Krause and Joachim M Buhmann. 2017. Continuous dr-submodular maximization: Structure and algorithms. In Advances in Neural Information Processing Systems. 486\u2013496.   An Bian Kfir Levy Andreas Krause and Joachim M Buhmann. 2017. Continuous dr-submodular maximization: Structure and algorithms. In Advances in Neural Information Processing Systems. 486\u2013496."},{"key":"e_1_3_2_1_13_1","unstructured":"Andrew An Bian Baharan Mirzasoleiman Joachim M Buhmann and Andreas Krause. 2016. Guaranteed non-convex optimization: Submodular maximization over continuous domains. arXiv preprint arXiv:1606.05615 (2016).  Andrew An Bian Baharan Mirzasoleiman Joachim M Buhmann and Andreas Krause. 2016. Guaranteed non-convex optimization: Submodular maximization over continuous domains. arXiv preprint arXiv:1606.05615 (2016)."},{"key":"e_1_3_2_1_14_1","unstructured":"Niv Buchbinder and Moran Feldman. 2016. Constrained submodular maximization via a non-symmetric technique. arXiv preprint arXiv:1611.03253 (2016).  Niv Buchbinder and Moran Feldman. 2016. Constrained submodular maximization via a non-symmetric technique. arXiv preprint arXiv:1611.03253 (2016)."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/080733991"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2688073.2688086"},{"key":"e_1_3_2_1_17_1","unstructured":"Chandra Chekuri and Kent Quanrud. 2018. Submodular Function Maximization in Parallel via the Multilinear Relaxation. arXiv preprint arXiv:1807.08678 (2018).   Chandra Chekuri and Kent Quanrud. 2018. Submodular Function Maximization in Parallel via the Multilinear Relaxation. arXiv preprint arXiv:1807.08678 (2018)."},{"key":"e_1_3_2_1_18_1","unstructured":"Alina Ene and Huy L Nguyen. 2018.  Alina Ene and Huy L Nguyen. 2018."},{"key":"e_1_3_2_1_19_1","unstructured":"Submodular Maximization with Nearlyoptimal Approximation and Adaptivity in Nearly-linear Time. arXiv preprint arXiv:1804.05379 (2018).  Submodular Maximization with Nearlyoptimal Approximation and Adaptivity in Nearly-linear Time. arXiv preprint arXiv:1804.05379 (2018)."},{"key":"e_1_3_2_1_20_1","unstructured":"Alina Ene Huy L Nguyen and Adrian Vladu. 2018. Submodular maximization with matroid and packing constraints in parallel. arXiv preprint arXiv:1808.09987 (2018).  Alina Ene Huy L Nguyen and Adrian Vladu. 2018. Submodular maximization with matroid and packing constraints in parallel. arXiv preprint arXiv:1808.09987 (2018)."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3087556.3087574"},{"key":"e_1_3_2_1_22_1","unstructured":"Matthew Fahrbach Vahab Mirrokni and Morteza Zadimoghaddam. 2018. Submodular Maximization with Optimal Approximation Adaptivity and Query Complexity. arXiv preprint arXiv:1807.07889 (2018).  Matthew Fahrbach Vahab Mirrokni and Morteza Zadimoghaddam. 2018. Submodular Maximization with Optimal Approximation Adaptivity and Query Complexity. arXiv preprint arXiv:1807.07889 (2018)."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.46"},{"key":"e_1_3_2_1_24_1","unstructured":"Andr\u00e1s Frank. 2011.  Andr\u00e1s Frank. 2011."},{"key":"e_1_3_2_1_25_1","unstructured":"Connections in combinatorial optimization. Vol. 38. OUP Oxford.  Connections in combinatorial optimization. Vol. 38. OUP Oxford."},{"key":"e_1_3_2_1_26_1","unstructured":"Ravi Kumar Benjamin Moseley Sergei Vassilvitskii and Andrea Vattani. 2013.  Ravi Kumar Benjamin Moseley Sergei Vassilvitskii and Andrea Vattani. 2013."},{"key":"e_1_3_2_1_27_1","volume-title":"Greedy Algorithms in Mapreduce and Streaming. In PACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 1\u201310","author":"Fast"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167211"},{"key":"e_1_3_2_1_29_1","volume-title":"LIPIcs-Leibniz International Proceedings in Informatics","volume":"55","author":"Mahoney Michael W","year":"2016"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746624"},{"key":"e_1_3_2_1_31_1","unstructured":"Baharan Mirzasoleiman Amin Karbasi Ashwinkumar Badanidiyuru and Andreas Krause. 2015.  Baharan Mirzasoleiman Amin Karbasi Ashwinkumar Badanidiyuru and Andreas Krause. 2015."},{"key":"e_1_3_2_1_32_1","unstructured":"Distributed submodular cover: Succinctly summarizing massive data. In Advances in Neural Information Processing Systems. 2881\u20132889.   Distributed submodular cover: Succinctly summarizing massive data. In Advances in Neural Information Processing Systems. 2881\u20132889."},{"key":"e_1_3_2_1_33_1","unstructured":"Baharan Mirzasoleiman Amin Karbasi Rik Sarkar and Andreas Krause. 2013.  Baharan Mirzasoleiman Amin Karbasi Rik Sarkar and Andreas Krause. 2013."},{"key":"e_1_3_2_1_34_1","volume-title":"Advances in Neural Information Processing Systems (NIPS). 2049\u2013","author":"Maximization Distributed Submodular","year":"2057"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcom.1994.1025"},{"key":"e_1_3_2_1_36_1","unstructured":"Rad Niazadeh Tim Roughgarden and Joshua R Wang. 2018. Optimal Algorithms for Continuous Non-monotone Submodular and DR-Submodular Maximization. arXiv preprint arXiv:1805.09480 (2018).  Rad Niazadeh Tim Roughgarden and Joshua R Wang. 2018. Optimal Algorithms for Continuous Non-monotone Submodular and DR-Submodular Maximization. arXiv preprint arXiv:1805.09480 (2018)."},{"key":"e_1_3_2_1_37_1","first-page":"898","article-title":"Non-Monotone DR-Submodular Function Maximization","volume":"17","author":"Soma Tasuku","year":"2017","journal-title":"AAAI"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374389"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2001.959930"}],"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.3316389","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3313276.3316389","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3313276.3316389","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:54:32Z","timestamp":1750204472000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313276.3316389"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,23]]},"references-count":39,"alternative-id":["10.1145\/3313276.3316389","10.1145\/3313276"],"URL":"https:\/\/doi.org\/10.1145\/3313276.3316389","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"}}]}}