{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,1]],"date-time":"2026-02-01T01:17:09Z","timestamp":1769908629755,"version":"3.49.0"},"publisher-location":"New York, NY, USA","reference-count":34,"publisher":"ACM","license":[{"start":{"date-parts":[[2023,8,4]],"date-time":"2023-08-04T00:00:00Z","timestamp":1691107200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-sa\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,8,6]]},"DOI":"10.1145\/3580305.3599259","type":"proceedings-article","created":{"date-parts":[[2023,8,4]],"date-time":"2023-08-04T18:10:58Z","timestamp":1691172658000},"page":"250-261","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Approximation Algorithms for Size-Constrained Non-Monotone Submodular Maximization in Deterministic Linear Time"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8611-2828","authenticated-orcid":false,"given":"Yixin","family":"Chen","sequence":"first","affiliation":[{"name":"Texas A&M University, College Station, TX, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6506-1902","authenticated-orcid":false,"given":"Alan","family":"Kuhnle","sequence":"additional","affiliation":[{"name":"Texas A&M University, College Station, TX, USA"}]}],"member":"320","published-online":{"date-parts":[[2023,8,4]]},"reference":[{"key":"e_1_3_2_2_1_1","volume-title":"47th International Colloquium on Automata, Languages, and Programming (ICALP). https:\/\/doi.org\/10","author":"Alaluf Naor","year":"2020","unstructured":"Naor Alaluf , Alina Ene , Moran Feldman , Huy L. Nguyen , and Andrew Suh . 2020 . Optimal streaming algorithms for submodular maximization with cardinality constraints. In 47th International Colloquium on Automata, Languages, and Programming (ICALP). https:\/\/doi.org\/10 .4230\/LIPIcs.ICALP.2020.6 arxiv: 1909.13676 10.4230\/LIPIcs.ICALP.2020.6 Naor Alaluf, Alina Ene, Moran Feldman, Huy L. Nguyen, and Andrew Suh. 2020. Optimal streaming algorithms for submodular maximization with cardinality constraints. In 47th International Colloquium on Automata, Languages, and Programming (ICALP). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2020.6 arxiv: 1909.13676"},{"key":"e_1_3_2_2_2_1","volume-title":"Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint. arXiv","author":"Amanatidis Georgios","year":"2020","unstructured":"Georgios Amanatidis , Federico Fusco , Philip Lazos , Stefano Leonardi , and Rebecca Reiffenh\u00e4 user. 2020. Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint. arXiv ( 2020 ), 1--23. arxiv: 2007.05014 Georgios Amanatidis, Federico Fusco, Philip Lazos, Stefano Leonardi, and Rebecca Reiffenh\u00e4 user. 2020. Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint. arXiv (2020), 1--23. arxiv: 2007.05014"},{"key":"#cr-split#-e_1_3_2_2_3_1.1","doi-asserted-by":"crossref","unstructured":"Ashwinkumar Badanidiyuru Baharan Mirzasoleiman Amin Karbasi and Andreas Krause. 2014. Streaming Submodular Maximization: Massive Data Summarization on the Fly. In ACM SIGKDD Knowledge Discovery and Data Mining (KDD). 671--680. https:\/\/doi.org\/10.1145\/2623330.2623637 10.1145\/2623330.2623637","DOI":"10.1145\/2623330.2623637"},{"key":"#cr-split#-e_1_3_2_2_3_1.2","doi-asserted-by":"crossref","unstructured":"Ashwinkumar Badanidiyuru Baharan Mirzasoleiman Amin Karbasi and Andreas Krause. 2014. Streaming Submodular Maximization: Massive Data Summarization on the Fly. In ACM SIGKDD Knowledge Discovery and Data Mining (KDD). 671--680. https:\/\/doi.org\/10.1145\/2623330.2623637","DOI":"10.1145\/2623330.2623637"},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.110"},{"key":"e_1_3_2_2_5_1","volume-title":"Mathematics of Operations Research","volume":"44","author":"Buchbinder Niv","year":"2016","unstructured":"Niv Buchbinder and Moran Feldman . 2016 . Constrained Submodular Maximization via a Non-symmetric Technique . Mathematics of Operations Research , Vol. 44 , 3 (2016). arxiv: 1611.03253 http:\/\/arxiv.org\/abs\/1611.03253 Niv Buchbinder and Moran Feldman. 2016. Constrained Submodular Maximization via a Non-symmetric Technique. Mathematics of Operations Research, Vol. 44, 3 (2016). arxiv: 1611.03253 http:\/\/arxiv.org\/abs\/1611.03253"},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3184990"},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.73"},{"key":"e_1_3_2_2_8_1","volume-title":"Submodular Maximization with Cardinality Constraints. In Symposium on Discrete Algorithms (SODA). ACM.","author":"Buchbinder Niv","year":"2014","unstructured":"Niv Buchbinder , Moran Feldman , Joseph Seffi Naor , and Roy Schwartz . 2014 b. Submodular Maximization with Cardinality Constraints. In Symposium on Discrete Algorithms (SODA). ACM. Niv Buchbinder, Moran Feldman, Joseph Seffi Naor, and Roy Schwartz. 2014b. Submodular Maximization with Cardinality Constraints. In Symposium on Discrete Algorithms (SODA). ACM."},{"key":"e_1_3_2_2_9_1","volume-title":"Online Submodular Maximization with Preemption. In ACM-SIAM Symposium on Discrete Algorithms. https:\/\/doi.org\/10","author":"Buchbinder Niv","year":"2014","unstructured":"Niv Buchbinder , Moran Feldman , and Roy Schwartz . 2014 a. Online Submodular Maximization with Preemption. In ACM-SIAM Symposium on Discrete Algorithms. https:\/\/doi.org\/10 .1137\/1.9781611973730.80 arxiv: 1501.05801 10.1137\/1.9781611973730.80 Niv Buchbinder, Moran Feldman, and Roy Schwartz. 2014a. Online Submodular Maximization with Preemption. In ACM-SIAM Symposium on Discrete Algorithms. https:\/\/doi.org\/10.1137\/1.9781611973730.80 arxiv: 1501.05801"},{"key":"e_1_3_2_2_10_1","volume-title":"Comparing Apples and Oranges: Query Tradeoff in Submodular Maximization. In ACM-SIAM Symposium on Discrete Algorithms (SODA). https:\/\/doi.org\/10","author":"Buchbinder Niv","year":"2015","unstructured":"Niv Buchbinder , Moran Feldman , and Roy Schwartz . 2015 . Comparing Apples and Oranges: Query Tradeoff in Submodular Maximization. In ACM-SIAM Symposium on Discrete Algorithms (SODA). https:\/\/doi.org\/10 .1137\/1.9781611973730.77 arxiv: 1410.0773 10.1137\/1.9781611973730.77 Niv Buchbinder, Moran Feldman, and Roy Schwartz. 2015. Comparing Apples and Oranges: Query Tradeoff in Submodular Maximization. In ACM-SIAM Symposium on Discrete Algorithms (SODA). https:\/\/doi.org\/10.1137\/1.9781611973730.77 arxiv: 1410.0773"},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-015-0900-7"},{"key":"e_1_3_2_2_12_1","volume-title":"ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Hubert Chan T. H.","year":"2017","unstructured":"T. H. Hubert Chan , Zhiyi Huang , Shaofeng H.C. Jiang , Ning Kang , and Zhihao Gavin Tang . 2017 . Online Submodular Maximization with Free Disposal: Randomization Beats 1\/4 for Partition Matroids . ACM-SIAM Symposium on Discrete Algorithms (SODA) (2017), 1204--1223. T. H.Hubert Chan, Zhiyi Huang, Shaofeng H.C. Jiang, Ning Kang, and Zhihao Gavin Tang. 2017. Online Submodular Maximization with Free Disposal: Randomization Beats 1\/4 for Partition Matroids. ACM-SIAM Symposium on Discrete Algorithms (SODA) (2017), 1204--1223."},{"key":"e_1_3_2_2_13_1","unstructured":"Chandra Chekuri Shalmoli Gupta and Kent Quanrud. 2015. Streaming Algorithms for Submodular Function Maximization. In International Colloquium on Automata Languages and Programming (ICALP). arxiv: 1504.08024 http:\/\/arxiv.org\/abs\/1504.08024  Chandra Chekuri Shalmoli Gupta and Kent Quanrud. 2015. Streaming Algorithms for Submodular Function Maximization. In International Colloquium on Automata Languages and Programming (ICALP). arxiv: 1504.08024 http:\/\/arxiv.org\/abs\/1504.08024"},{"key":"e_1_3_2_2_14_1","unstructured":"Ethan R. Elenberg Alexandros G. Dimakis Moran Feldman and Amin Karbasi. 2017. Streaming Weak Submodularity: Interpreting Neural Networks on the Fly. In Advances in Neural Information Processing Systems (NeurIPS). arxiv: 1703.02647 http:\/\/arxiv.org\/abs\/1703.02647  Ethan R. Elenberg Alexandros G. Dimakis Moran Feldman and Amin Karbasi. 2017. Streaming Weak Submodularity: Interpreting Neural Networks on the Fly. In Advances in Neural Information Processing Systems (NeurIPS). arxiv: 1703.02647 http:\/\/arxiv.org\/abs\/1703.02647"},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1214\/17-AOS1679"},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.17"},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/090750688"},{"key":"e_1_3_2_2_18_1","volume-title":"Conference on Learning Theory (COLT). arxiv: 1704","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). arxiv: 1704 .01652 http:\/\/arxiv.org\/abs\/1704.01652 Moran Feldman, Christopher Harshaw, and Amin Karbasi. 2017. Greed is Good: Near-Optimal Submodular Maximization via Greedy Optimization. In Conference on Learning Theory (COLT). arxiv: 1704.01652 http:\/\/arxiv.org\/abs\/1704.01652"},{"key":"e_1_3_2_2_19_1","volume-title":"Do less","author":"Feldman Moran","year":"1802","unstructured":"Moran Feldman , Amin Karbasi , and Ehsan Kazemi . 2018. Do less , Get More : Streaming Submodular Maximization with Subsampling. In Advances in Neural Information Processing Systems (NeurIPS) . arxiv: 1802 .07098 http:\/\/arxiv.org\/abs\/1802.07098 Moran Feldman, Amin Karbasi, and Ehsan Kazemi. 2018. Do less, Get More: Streaming Submodular Maximization with Subsampling. In Advances in Neural Information Processing Systems (NeurIPS). arxiv: 1802.07098 http:\/\/arxiv.org\/abs\/1802.07098"},{"key":"e_1_3_2_2_20_1","volume-title":"The One-way Communication Complexity of Submodular Maximization with Applications to Streaming and Robustness. In arXiv preprint arXiv:2003.13459. arxiv","author":"Feldman Moran","year":"2003","unstructured":"Moran Feldman , Ashkan Norouzi-Fard , Ola Svensson , and Rico Zenklusen . 2020. The One-way Communication Complexity of Submodular Maximization with Applications to Streaming and Robustness. In arXiv preprint arXiv:2003.13459. arxiv : 2003 .13459 http:\/\/arxiv.org\/abs\/2003.13459 Moran Feldman, Ashkan Norouzi-Fard, Ola Svensson, and Rico Zenklusen. 2020. The One-way Communication Complexity of Submodular Maximization with Applications to Streaming and Robustness. In arXiv preprint arXiv:2003.13459. arxiv: 2003.13459 http:\/\/arxiv.org\/abs\/2003.13459"},{"key":"e_1_3_2_2_21_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 k-Set System Constraint . In International Conference on Machine Learning (ICML). Ran Haba, Ehsan Kazemi, Moran Feldman, and Amin Karbasi. 2020. Streaming Submodular Maximization under a k-Set System Constraint. In International Conference on Machine Learning (ICML)."},{"key":"e_1_3_2_2_22_1","volume-title":"International Conference on World Wide Web (WWW)","author":"Hartline Jason","year":"2008","unstructured":"Jason Hartline , Vahab S. Mirrokni , and Mukund Sundararajan . 2008 . Optimal marketing strategies over social networks . International Conference on World Wide Web (WWW) (2008), 189--198. https:\/\/doi.org\/10.1145\/1367497.1367524 10.1145\/1367497.1367524 Jason Hartline, Vahab S. Mirrokni, and Mukund Sundararajan. 2008. Optimal marketing strategies over social networks. International Conference on World Wide Web (WWW) (2008), 189--198. https:\/\/doi.org\/10.1145\/1367497.1367524"},{"key":"e_1_3_2_2_23_1","volume-title":"Algorithmic Learning Theory. arxiv","author":"Iyer Rishabh","year":"2006","unstructured":"Rishabh Iyer , Ninad Khargonkar , Jeff Bilmes , and Himanshu Asnani . 2020. Submodular Combinatorial Information Measures with Applications in Machine Learning . In Algorithmic Learning Theory. arxiv : 2006 .15412 http:\/\/arxiv.org\/abs\/2006.15412 Rishabh Iyer, Ninad Khargonkar, Jeff Bilmes, and Himanshu Asnani. 2020. Submodular Combinatorial Information Measures with Applications in Machine Learning. In Algorithmic Learning Theory. arxiv: 2006.15412 http:\/\/arxiv.org\/abs\/2006.15412"},{"key":"e_1_3_2_2_24_1","unstructured":"Alan Kuhnle. 2019. Interlaced Greedy Algorithm for Maximization of Submodular Functions in Nearly Linear Time. In Advances in Neural Information Processing Systems (NeurIPS).  Alan Kuhnle. 2019. Interlaced Greedy Algorithm for Maximization of Submodular Functions in Nearly Linear Time. In Advances in Neural Information Processing Systems (NeurIPS)."},{"key":"e_1_3_2_2_25_1","unstructured":"Alan Kuhnle. 2021. Streaming Algorithms for Cardinality-Constrained Maximization of Non-Monotone Submodular Functions in Linear Time. In arXiv:2104.06873. arxiv: 2104.06873 http:\/\/arxiv.org\/abs\/2104.06873  Alan Kuhnle. 2021. Streaming Algorithms for Cardinality-Constrained Maximization of Non-Monotone Submodular Functions in Linear Time. In arXiv:2104.06873. arxiv: 2104.06873 http:\/\/arxiv.org\/abs\/2104.06873"},{"key":"e_1_3_2_2_26_1","unstructured":"Jure Leskovec and Andrej Krevl. 2020. SNAP Datasets: Stanford Large Network Dataset Collection. \\url{http:\/\/snap.stanford.edu\/data}.  Jure Leskovec and Andrej Krevl. 2020. SNAP Datasets: Stanford Large Network Dataset Collection. \\url{http:\/\/snap.stanford.edu\/data}."},{"key":"e_1_3_2_2_27_1","volume-title":"Choosing non-redundant representative subsets of protein sequence data sets using submodular optimization. Proteins: Structure, Function, and Bioinformatics","author":"Libbrecht Maxwell W","year":"2017","unstructured":"Maxwell W Libbrecht , Jeffrey A Bilmes , and William Stafford . 2017. Choosing non-redundant representative subsets of protein sequence data sets using submodular optimization. Proteins: Structure, Function, and Bioinformatics July 2017 (2017), 454--466. https:\/\/doi.org\/10.1002\/prot.25461 10.1002\/prot.25461 Maxwell W Libbrecht, Jeffrey A Bilmes, and William Stafford. 2017. Choosing non-redundant representative subsets of protein sequence data sets using submodular optimization. Proteins: Structure, Function, and Bioinformatics July 2017 (2017), 454--466. https:\/\/doi.org\/10.1002\/prot.25461"},{"key":"e_1_3_2_2_28_1","unstructured":"Paul Liu Aviad Rubinstein Jan Vondrak and Junyao Zhao. 2021. Cardinality constrained submodular maximization for random streams. In Advances in Neural Information Processing Systems 34. arxiv: 2111.07217 http:\/\/arxiv.org\/abs\/2111.07217  Paul Liu Aviad Rubinstein Jan Vondrak and Junyao Zhao. 2021. Cardinality constrained submodular maximization for random streams. In Advances in Neural Information Processing Systems 34. arxiv: 2111.07217 http:\/\/arxiv.org\/abs\/2111.07217"},{"key":"e_1_3_2_2_29_1","volume-title":"Lazier Than Lazy Greedy. In AAAI Conference on Artificial Intelligence (AAAI). arxiv: 1409","author":"Mirzasoleiman Baharan","year":"2015","unstructured":"Baharan Mirzasoleiman , Ashwinkumar Badanidiyuru , Amin Karbasi , Jan Vondrak , and Andreas Krause . 2015 . Lazier Than Lazy Greedy. In AAAI Conference on Artificial Intelligence (AAAI). arxiv: 1409 .7938 http:\/\/arxiv.org\/abs\/1409.7938 Baharan Mirzasoleiman, Ashwinkumar Badanidiyuru, Amin Karbasi, Jan Vondrak, and Andreas Krause. 2015. Lazier Than Lazy Greedy. In AAAI Conference on Artificial Intelligence (AAAI). arxiv: 1409.7938 http:\/\/arxiv.org\/abs\/1409.7938"},{"key":"e_1_3_2_2_30_1","volume-title":"Streaming Non-Monotone Submodular Maximization: Personalized Video Summarization on the Fly. In AAAI Conference on Artificial Intelligence. arxiv: 1706","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 AAAI Conference on Artificial Intelligence. arxiv: 1706 .03583 http:\/\/arxiv.org\/abs\/1706.03583 Baharan Mirzasoleiman, Stefanie Jegelka, and Andreas Krause. 2018. Streaming Non-Monotone Submodular Maximization: Personalized Video Summarization on the Fly. In AAAI Conference on Artificial Intelligence. arxiv: 1706.03583 http:\/\/arxiv.org\/abs\/1706.03583"},{"key":"e_1_3_2_2_31_1","volume-title":"Growth of the Flickr Social Network. In First Workshop on Online Social Networks.","author":"Mislove Alan","year":"2008","unstructured":"Alan Mislove , Hema Swetha Koppula , Krishna P Gummadi , Peter Druschel , and Bobby Bhattacharjee . 2008 . Growth of the Flickr Social Network. In First Workshop on Online Social Networks. Alan Mislove, Hema Swetha Koppula, Krishna P Gummadi, Peter Druschel, and Bobby Bhattacharjee. 2008. Growth of the Flickr Social Network. In First Workshop on Online Social Networks."},{"key":"e_1_3_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.3.3.177"},{"key":"e_1_3_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01588971"}],"event":{"name":"KDD '23: The 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining","location":"Long Beach CA USA","acronym":"KDD '23","sponsor":["SIGMOD ACM Special Interest Group on Management of Data","SIGKDD ACM Special Interest Group on Knowledge Discovery in Data"]},"container-title":["Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3580305.3599259","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3580305.3599259","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:51:15Z","timestamp":1750182675000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3580305.3599259"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,8,4]]},"references-count":34,"alternative-id":["10.1145\/3580305.3599259","10.1145\/3580305"],"URL":"https:\/\/doi.org\/10.1145\/3580305.3599259","relation":{},"subject":[],"published":{"date-parts":[[2023,8,4]]},"assertion":[{"value":"2023-08-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}