{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,23]],"date-time":"2026-01-23T11:08:36Z","timestamp":1769166516791,"version":"3.49.0"},"reference-count":46,"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\/100000001","name":"National Science Foundation Grant","doi-asserted-by":"crossref","award":["CNS-1951952"],"award-info":[{"award-number":["CNS-1951952"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["61772491"],"award-info":[{"award-number":["61772491"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["U1709217"],"award-info":[{"award-number":["U1709217"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001381","name":"Singapore National Research Foundation","doi-asserted-by":"crossref","award":["NRF-RSS2016-004"],"award-info":[{"award-number":["NRF-RSS2016-004"]}],"id":[{"id":"10.13039\/501100001381","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Singapore Ministry of Education Academic Research Fund Tier 1","award":["MOE2019-T1-002-042"],"award-info":[{"award-number":["MOE2019-T1-002-042"]}]},{"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"}]},{"name":"Anhui Initiative in Quantum Information Technologies","award":["AHY150300"],"award-info":[{"award-number":["AHY150300"]}]}],"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>Monotone submodular maximization with a knapsack constraint is NP-hard. Various approximation algorithms have been devised to address this optimization problem. In this paper, we revisit the widely known modified greedy algorithm. First, we show that this algorithm can achieve an approximation factor of 0.405, which significantly improves the known factors of 0.357 given by Wolsey and (1-1\/e)\/2\\approx 0.316 given by Khuller et al. More importantly, our analysis closes a gap in Khuller et al.'s proof for the extensively mentioned approximation factor of (1-1\/\\sqrte )\\approx 0.393 in the literature to clarify a long-standing misconception on this issue. Second, we enhance the modified greedy algorithm to derive a data-dependent upper bound on the optimum. We empirically demonstrate the tightness of our upper bound with a real-world application. The bound enables us to obtain a data-dependent ratio typically much higher than 0.405 between the solution value of the modified greedy algorithm and the optimum. It can also be used to significantly improve the efficiency of algorithms such as branch and bound.<\/jats:p>","DOI":"10.1145\/3447386","type":"journal-article","created":{"date-parts":[[2021,2,22]],"date-time":"2021-02-22T22:23:33Z","timestamp":1614032613000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["Revisiting Modified Greedy Algorithm for Monotone Submodular Maximization with a Knapsack Constraint"],"prefix":"10.1145","volume":"5","author":[{"given":"Jing","family":"Tang","sequence":"first","affiliation":[{"name":"National University of Singapore, Singapore, Singapore"}]},{"given":"Xueyan","family":"Tang","sequence":"additional","affiliation":[{"name":"Nanyang Technological University, Singapore, Singapore"}]},{"given":"Andrew","family":"Lim","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore, Singapore"}]},{"given":"Kai","family":"Han","sequence":"additional","affiliation":[{"name":"University of Science and Technology of China, Hefei, China"}]},{"given":"Chongshou","family":"Li","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore, Singapore"}]},{"given":"Junsong","family":"Yuan","sequence":"additional","affiliation":[{"name":"State University of New York at Buffalo, Buffalo, NY, USA"}]}],"member":"320","published-online":{"date-parts":[[2021,2,22]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(99)00103-1"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.110"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(73)80033-9"},{"key":"e_1_2_1_4_1","first-page":"105","article-title":"Interactive Graph Cuts for Optimal Boundary & Region Segmentation of Objects in N-D Images","volume":"1","author":"Boykov Yuri Y","year":"2001","unstructured":"Yuri Y Boykov and Marie-Pierre Jolly. 2001. Interactive Graph Cuts for Optimal Boundary & Region Segmentation of Objects in N-D Images. In Proc. IEEE ICCV, Vol. 1. 105--112.","journal-title":"Proc. IEEE ICCV"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/080733991"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(84)90003-9"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.23.8.789"},{"key":"e_1_2_1_8_1","volume-title":"Proc. NeurIPS . 962--970","author":"Delong Andrew","year":"2012","unstructured":"Andrew Delong, Olga Veksler, Anton Osokin, and Yuri Boykov. 2012. Minimizing Sparse High-Order Energies by Submodular Vertex-Cover. In Proc. NeurIPS . 962--970."},{"key":"e_1_2_1_9_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 Proc. ICALP. 53:1--53:12.","journal-title":"Proc. ICALP."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.45.11.1539"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/3213880.3213883"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-020-00615-8"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00062"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2011.5995589"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956769"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/11523468_91"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(99)00031-9"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.43.4.684"},{"key":"e_1_2_1_20_1","volume-title":"Proc. UAI . 324--331","author":"Krause Andreas","year":"2005","unstructured":"Andreas Krause and Carlos Guestrin. 2005. Near-Optimal Nonmyopic Value of Information in Graphical Models. In Proc. UAI . 324--331."},{"key":"e_1_2_1_21_1","volume-title":"Proc. AAAI . 1650--1654","author":"Krause Andreas","year":"2007","unstructured":"Andreas Krause and Carlos Guestrin. 2007. Near-Optimal Observation Selection using Submodular Functions. In Proc. AAAI . 1650--1654."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1061\/(ASCE)0733-9496(2008)134:6(516)"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/1390681.1390689"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772751"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281192.1281239"},{"key":"e_1_2_1_26_1","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford.edu\/data ."},{"key":"e_1_2_1_27_1","volume-title":"Proc. NAACL-HLT. 912--920","author":"Lin Hui","year":"2010","unstructured":"Hui Lin and Jeff Bilmes. 2010. Multi-Document Summarization via Budgeted Maximization of Submodular Functions. In Proc. NAACL-HLT. 912--920."},{"key":"e_1_2_1_28_1","volume-title":"Proc. HLT . 510--520","author":"Lin Hui","year":"2011","unstructured":"Hui Lin and Jeff Bilmes. 2011. A Class of Submodular Functions for Document Summarization. In Proc. HLT . 510--520."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.3.3.177"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01588971"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/2893873.2893897"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1080\/02664768700000020"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(03)00062-2"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973730.76"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319881"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3183749"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICNP.2016.7784445"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3110025.3110041"},{"key":"e_1_2_1_39_1","volume-title":"Social Network Analysis and Mining","volume":"8","author":"Tang Jing","year":"2018","unstructured":"Jing Tang, Xueyan Tang, and Junsong Yuan. 2018a. An Efficient and Effective Hop-Based Approach for Inluence Maximization in Social Networks. Social Network Analysis and Mining , Vol. 8, 10 (2018)."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2017.2787757"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2018.8485975"},{"key":"e_1_2_1_42_1","volume-title":"Proc. ICML . 1954--1963","author":"Wei Kai","year":"2015","unstructured":"Kai Wei, Rishabh Iyer, and Jeff Bilmes. 2015. Submodularity in Data Subset Selection and Active Learning. In Proc. ICML . 1954--1963."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.7.3.410"},{"key":"e_1_2_1_44_1","unstructured":"Yuichi Yoshida. 2016. Maximizing a Monotone Submodular Function with a Bounded Curvature under a Knapsack Constraint. arXiv preprint http:\/\/arxiv.org\/abs\/1607.04527 ."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v30i1.10146"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3219946"}],"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\/3447386","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3447386","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\/3447386"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,2,18]]},"references-count":46,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,2,18]]}},"alternative-id":["10.1145\/3447386"],"URL":"https:\/\/doi.org\/10.1145\/3447386","relation":{},"ISSN":["2476-1249"],"issn-type":[{"value":"2476-1249","type":"electronic"}],"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"}}]}}