{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,14]],"date-time":"2025-11-14T03:58:00Z","timestamp":1763092680203,"version":"3.41.0"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2021,2,18]],"date-time":"2021-02-18T00:00:00Z","timestamp":1613606400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61772491"],"award-info":[{"award-number":["61772491"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100012166","name":"National Key R&D Program of China","doi-asserted-by":"crossref","award":["2018AAA0101204"],"award-info":[{"award-number":["2018AAA0101204"]}],"id":[{"id":"10.13039\/501100012166","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Meas. Anal. Comput. Syst."],"published-print":{"date-parts":[[2021,2,18]]},"abstract":"<jats:p>Data summarization, i.e., selecting representative subsets of manageable size out of massive data, is often modeled as a submodular optimization problem. Although there exist extensive algorithms for submodular optimization, many of them incur large computational overheads and hence are not suitable for mining big data. In this work, we consider the fundamental problem of (non-monotone) submodular function maximization with a knapsack constraint, and propose simple yet effective and efficient algorithms for it. Specifically, we propose a deterministic algorithm with approximation ratio 6 and a randomized algorithm with approximation ratio 4, and show that both of them can be accelerated to achieve nearly linear running time at the cost of weakening the approximation ratio by an additive factor of \u03b5. We then consider a more restrictive setting without full access to the whole dataset, and propose streaming algorithms with approximation ratios of 8+\u03b5 and 6+\u03b5 that make one pass and two passes over the data stream, respectively. As a by-product, we also propose a two-pass streaming algorithm with an approximation ratio of 2+\u03b5 when the considered submodular function is monotone. To the best of our knowledge, our algorithms achieve the best performance bounds compared to the state-of-the-art approximation algorithms with efficient implementation for the same problem. Finally, we evaluate our algorithms in two concrete submodular data summarization applications for revenue maximization in social networks and image summarization, and the empirical results show that our algorithms outperform the existing ones in terms of both effectiveness and efficiency.<\/jats:p>","DOI":"10.1145\/3447383","type":"journal-article","created":{"date-parts":[[2021,2,22]],"date-time":"2021-02-22T22:23:33Z","timestamp":1614032613000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["Approximation Algorithms for Submodular Data Summarization with a Knapsack Constraint"],"prefix":"10.1145","volume":"5","author":[{"given":"Kai","family":"Han","sequence":"first","affiliation":[{"name":"University of Science and Technology of China, HeFei, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shuang","family":"Cui","sequence":"additional","affiliation":[{"name":"University of Science and Technology of China, HeFei, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tianshuai","family":"Zhu","sequence":"additional","affiliation":[{"name":"University of Science and Technology of China, HeFei, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Enpei","family":"Zhang","sequence":"additional","affiliation":[{"name":"University of Science and Technology of China, HeFei, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Benwei","family":"Wu","sequence":"additional","affiliation":[{"name":"University of Science and Technology of China, HeFei, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhizhuo","family":"Yin","sequence":"additional","affiliation":[{"name":"University of Science and Technology of China, HeFei, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tong","family":"Xu","sequence":"additional","affiliation":[{"name":"University of Science and Technology of China, HeFei, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shaojie","family":"Tang","sequence":"additional","affiliation":[{"name":"University of Texas at Dallas, Dallas, TX, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"He","family":"Huang","sequence":"additional","affiliation":[{"name":"Soochow University, SuZhou, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,2,22]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Neural Information Processing Systems (NeurIPS), arXiv","author":"Amanatidis Georgios","year":"2007","unstructured":"Georgios Amanatidis, Federico Fusco, Philip Lazos, Stefano Leonardi, and Rebecca Reiffenh\u00e4user. 2020. Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint. In Neural Information Processing Systems (NeurIPS), arXiv: 2007.05014."},{"doi-asserted-by":"publisher","key":"e_1_2_1_2_1","DOI":"10.1145\/2623330.2623637"},{"doi-asserted-by":"publisher","key":"e_1_2_1_3_1","DOI":"10.1137\/1.9781611973402.110"},{"unstructured":"Eric Balkanski Adam Breuer and Yaron Singer. 2018. Non-monotone submodular maximization in exponentially fewer iterations. In Neural Information Processing Systems (NeurIPS). 2353--2364.","key":"e_1_2_1_4_1"},{"key":"e_1_2_1_5_1","volume-title":"International Conference on Machine Learning (ICML). 515--523","author":"Bateni Mohammadhossein","year":"2019","unstructured":"Mohammadhossein Bateni, Lin Chen, Hossein Esfandiari, Thomas Fu, Vahab Mirrokni, and Afshin Rostamizadeh. 2019. Categorical feature compression via submodular optimization. In International Conference on Machine Learning (ICML). 515--523."},{"doi-asserted-by":"publisher","key":"e_1_2_1_6_1","DOI":"10.1145\/3184990"},{"doi-asserted-by":"publisher","key":"e_1_2_1_7_1","DOI":"10.1287\/moor.2018.0955"},{"doi-asserted-by":"publisher","key":"e_1_2_1_8_1","DOI":"10.1137\/1.9781611975482.16"},{"doi-asserted-by":"publisher","key":"e_1_2_1_9_1","DOI":"10.1137\/1.9781611973402.106"},{"doi-asserted-by":"publisher","key":"e_1_2_1_10_1","DOI":"10.1137\/130929205"},{"doi-asserted-by":"crossref","unstructured":"Chandra Chekuri Shalmoli Gupta and Kent Quanrud. 2015. Streaming algorithms for submodular function maximization. In International Colloquium on Automata Languages and Programming (ICALP). 318--330.","key":"e_1_2_1_11_1","DOI":"10.1007\/978-3-662-47672-7_26"},{"doi-asserted-by":"crossref","unstructured":"Chandra Chekuri TS Jayram and Jan Vondr\u00e1k. 2015. On multiplicative weight updates for concave and submodular function maximization. In Innovations in Theoretical Computer Science (ITCS). 201--210.","key":"e_1_2_1_12_1","DOI":"10.1145\/2688073.2688086"},{"unstructured":"Liang-Chieh Chen Maxwell Collins Yukun Zhu George Papandreou Barret Zoph Florian Schroff Hartwig Adam and Jon Shlens. 2018. Searching for efficient multi-scale architectures for dense image prediction. In Advances in neural information processing systems (NeurIPS). 8699--8710.","key":"e_1_2_1_13_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_14_1","DOI":"10.1145\/1557019.1557047"},{"doi-asserted-by":"publisher","key":"e_1_2_1_15_1","DOI":"10.1109\/FOCS.2016.34"},{"key":"e_1_2_1_16_1","first-page":"1","article-title":"A nearly-linear time algorithm for submodular maximization with a knapsack constraint","volume":"53","author":"Ene Alina","year":"2019","unstructured":"Alina Ene and Huy L. Nguyen. 2019. A nearly-linear time algorithm for submodular maximization with a knapsack constraint. In International Colloquium on Automata, Languages, and Programming (ICALP). 53:1--53:12.","journal-title":"International Colloquium on Automata, Languages, and Programming (ICALP)."},{"key":"e_1_2_1_17_1","volume-title":"International Conference on Machine Learning (ICML). 1833--","author":"Fahrbach Matthew","year":"2019","unstructured":"Matthew Fahrbach, Vahab Mirrokni, and Morteza Zadimoghaddam. 2019. Non-monotone submodular maximization with nearly optimal adaptivity and query complexity. In International Conference on Machine Learning (ICML). 1833-- 1842."},{"doi-asserted-by":"publisher","key":"e_1_2_1_18_1","DOI":"10.1137\/090779346"},{"key":"e_1_2_1_19_1","volume-title":"Conference on Learning Theory (COLT). 758--784","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 Conference on Learning Theory (COLT). 758--784."},{"doi-asserted-by":"publisher","key":"e_1_2_1_20_1","DOI":"10.1109\/FOCS.2011.46"},{"doi-asserted-by":"publisher","key":"e_1_2_1_21_1","DOI":"10.1137\/1.9781611973082.83"},{"key":"e_1_2_1_22_1","volume-title":"International Conference on Machine Learning (ICML). 391--398","author":"Gomes Ryan","year":"2010","unstructured":"Ryan Gomes and Andreas Krause. 2010. Budgeted nonparametric learning from data streams. In International Conference on Machine Learning (ICML). 391--398."},{"doi-asserted-by":"publisher","key":"e_1_2_1_23_1","DOI":"10.1007\/978-3-642-17572-5_20"},{"key":"e_1_2_1_24_1","volume-title":"International Conference on Machine Learning (ICML).","author":"Haba Ran","year":"2020","unstructured":"Ran Haba, Ehsan Kazemi, Moran Feldman, and Amin Karbasi. 2020. Streaming Submodular Maximization under a ??-Set System Constraint. In International Conference on Machine Learning (ICML)."},{"unstructured":"Shengyuan Hu Tao Yu Chuan Guo Wei-Lun Chao and Kilian Q Weinberger. 2019. A new defense against adversarial images: Turning a weakness into a strength. In Advances in neural information processing systems (NeurIPS). 1635--1646.","key":"e_1_2_1_25_1"},{"key":"e_1_2_1_26_1","volume-title":"Multi-Pass Streaming Algorithms for Monotone Submodular Function Maximization. preprint, arXiv:1802.06212","author":"Huang Chien-Chung","year":"2018","unstructured":"Chien-Chung Huang and Naonori Kakimura. 2018. Multi-Pass Streaming Algorithms for Monotone Submodular Function Maximization. preprint, arXiv:1802.06212 (2018)."},{"doi-asserted-by":"publisher","key":"e_1_2_1_27_1","DOI":"10.1007\/978-3-030-24766-9_32"},{"doi-asserted-by":"publisher","key":"e_1_2_1_28_1","DOI":"10.1007\/s00453-019-00628-y"},{"key":"e_1_2_1_29_1","volume-title":"International Conference on Machine Learning (ICML). 3311--3320","author":"Kazemi Ehsan","year":"2019","unstructured":"Ehsan Kazemi, Marko Mitrovic, Morteza Zadimoghaddam, Silvio Lattanzi, and Amin Karbasi. 2019. Submodular streaming in all Its glory: Tight approximation, minimum memory and low adaptive complexity. In International Conference on Machine Learning (ICML). 3311--3320."},{"doi-asserted-by":"publisher","key":"e_1_2_1_30_1","DOI":"10.1016\/S0020-0190(99)00031-9"},{"key":"e_1_2_1_31_1","volume-title":"Tractability: Practical Approaches to Hard Problems","author":"Krause Andreas","year":"2014","unstructured":"Andreas Krause and Daniel Golovin. 2014. Tractability: Practical Approaches to Hard Problems. Cambridge University Press. 71--104 pages."},{"unstructured":"Alan Kuhnle. 2019. Interlaced greedy algorithm for maximization of submodular functions in nearly linear time. In Neural Information Processing Systems (NeurIPS). 2371--2381.","key":"e_1_2_1_33_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_34_1","DOI":"10.1287\/moor.2013.0592"},{"doi-asserted-by":"publisher","key":"e_1_2_1_35_1","DOI":"10.1145\/1536414.1536459"},{"doi-asserted-by":"publisher","key":"e_1_2_1_36_1","DOI":"10.1145\/1281192.1281239"},{"unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP datasets: Stanford large network dataset collection URL: https:\/\/snap.stanford.edu.","key":"e_1_2_1_37_1"},{"key":"e_1_2_1_38_1","volume-title":"Nearly linear time algorithms and lower bound for submodular maximization. preprint, arXiv:1804.08178","author":"Li Wenxin","year":"2018","unstructured":"Wenxin Li and Ness Shroff. 2018. Nearly linear time algorithms and lower bound for submodular maximization. preprint, arXiv:1804.08178 (2018)."},{"doi-asserted-by":"publisher","key":"e_1_2_1_39_1","DOI":"10.1109\/ICDE.2017.137"},{"key":"e_1_2_1_40_1","volume-title":"Fast Constrained Submodular Maximization: Personalized Data Summarization. In International Conference on Machine Learning (ICML). 1358--1367","author":"Mirzasoleiman Baharan","year":"2016","unstructured":"Baharan Mirzasoleiman, Ashwinkumar Badanidiyuru, and Amin Karbasi. 2016. Fast Constrained Submodular Maximization: Personalized Data Summarization. In International Conference on Machine Learning (ICML). 1358--1367."},{"doi-asserted-by":"publisher","key":"e_1_2_1_41_1","DOI":"10.1609\/aaai.v32i1.11529"},{"doi-asserted-by":"publisher","key":"e_1_2_1_42_1","DOI":"10.1109\/INFOCOM.2019.8737400"},{"doi-asserted-by":"publisher","key":"e_1_2_1_43_1","DOI":"10.1109\/ICNP.2019.8888148"},{"doi-asserted-by":"publisher","key":"e_1_2_1_44_1","DOI":"10.1609\/aaai.v30i1.10207"},{"doi-asserted-by":"publisher","key":"e_1_2_1_45_1","DOI":"10.1145\/2396761.2396857"},{"doi-asserted-by":"publisher","key":"e_1_2_1_46_1","DOI":"10.1016\/S0167-6377(03)00062-2"},{"doi-asserted-by":"publisher","key":"e_1_2_1_47_1","DOI":"10.1287\/moor.7.3.410"},{"key":"e_1_2_1_48_1","volume-title":"International Conference on Artificial Intelligence and Statistics (AISTATS). 3263--3274","author":"Yaroslavtsev Grigory","year":"2020","unstructured":"Grigory Yaroslavtsev, Samson Zhou, and Dmitrii Avdiukhin. 2020. \"Bring your own greedy\" + max: Near-optimal 1\/2- approximations for submodular knapsack. In International Conference on Artificial Intelligence and Statistics (AISTATS). 3263--3274."},{"doi-asserted-by":"publisher","key":"e_1_2_1_49_1","DOI":"10.1609\/aaai.v33i01.33015861"}],"container-title":["Proceedings of the ACM on Measurement and Analysis of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3447383","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3447383","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:46:56Z","timestamp":1750193216000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3447383"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,2,18]]},"references-count":48,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,2,18]]}},"alternative-id":["10.1145\/3447383"],"URL":"https:\/\/doi.org\/10.1145\/3447383","relation":{},"ISSN":["2476-1249"],"issn-type":[{"type":"electronic","value":"2476-1249"}],"subject":[],"published":{"date-parts":[[2021,2,18]]},"assertion":[{"value":"2021-02-22","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}