More Web Proxy on the site http://driver.im/

research-article

Open access

Approximation Algorithms for Size-Constrained Non-Monotone Submodular Maximization in Deterministic Linear Time

Authors:

Alan KuhnleAuthors Info & Claims

KDD '23: Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining

Pages 250 - 261

https://doi.org/10.1145/3580305.3599259

Published: 04 August 2023 Publication History

Abstract

In this work, we study the problem of finding the maximum value of a non-negative submodular function subject to a limit on the number of items selected, a ubiquitous problem that appears in many applications, such as data summarization and nonlinear regression. We provide the first deterministic, linear-time approximation algorithms for this problem that do not assume the objective is monotone. We present three deterministic, linear-time algorithms: a single-pass streaming algorithm with a ratio of 23.313 + ε, which is the first linear-time streaming algorithm; a simpler deterministic linear-time algorithm with a ratio of 11.657; and a (4 + O(ε))-approximation algorithm. Finally, we present a deterministic algorithm that obtains ratio of e + ε in O_ε (n log(n)) time, close to the best known expected ratio of e - 0.121 in polynomial time.

Supplementary Material

MP4 File (rtfp1009-2min-promo.mp4)

A brief introduction of our work which focuses on deterministic, linear-time, combinatorial, non-monotone submodular maximization algorithms.

Download
14.32 MB

References

[1]

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

[2]

Georgios Amanatidis, Federico Fusco, Philip Lazos, Stefano Leonardi, and Rebecca Reiffenhä user. 2020. Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint. arXiv (2020), 1--23. arxiv: 2007.05014

[3]

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

Digital Library

[4]

Ashwinkumar Badanidiyuru and Jan Vondrá k. 2014. Fast algorithms for maximizing submodular functions. In ACM-SIAM Symposium on Discrete Algorithms (SODA). https://doi.org/10.1137/1.9781611973402.110

[5]

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

[6]

Niv Buchbinder and Moran Feldman. 2018. Deterministic Algorithms for Submodular Maximization. ACM Transactions on Algorithms, Vol. 14, 3 (2018).

Digital Library

[7]

Niv Buchbinder, Moran Feldman, Joseph Seffi Naor, and Roy Schwartz. 2012. A Tight Linear Time (1 / 2)-Approximation for Unconstrained Submodular Maximization. In Symposium on Foundations of Computer Science (FOCS). https://doi.org/10.1109/FOCS.2012.73

Digital Library

[8]

Niv Buchbinder, Moran Feldman, Joseph Seffi Naor, and Roy Schwartz. 2014b. Submodular Maximization with Cardinality Constraints. In Symposium on Discrete Algorithms (SODA). ACM.

[9]

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

[10]

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

[11]

Amit Chakrabarti and Sagar Kale. 2015. Submodular maximization meets streaming: matchings, matroids, and more. Mathematical Programming, Vol. 154, 1--2 (2015), 225--247. https://doi.org/10.1007/s10107-015-0900-7

Digital Library

[12]

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.

[13]

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

[14]

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

[15]

Ethan R. Elenberg, Rajiv Khanna, Alexandros G. Dimakis, and Sahand Negahban. 2018. Restricted strong convexity implies weak submodularity. Annals of Statistics, Vol. 46, 6B (2018), 3539--3568. https://doi.org/10.1214/17-AOS1679

[16]

Matthew Fahrbach, Vahab Mirrokni, and Morteza Zadimoghaddam. 2019. Submodular Maximization with Nearly Optimal Approximation, Adaptivity, and Query Complexity. In ACM-SIAM Symposium on Discrete Algorithms (SODA). 255--273. arxiv: 1808.06932

[17]

Uriel Feige, Vahab S. Mirrokni, and Jan Vondrá k. 2011. Maximizing Non-Monotone Submodular Functions. SIAM J. Comput., Vol. 40, 4 (2011), 1133--1153. https://doi.org/10.1137/090750688 arxiv: arXiv:1302.5877

Digital Library

[18]

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

[19]

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

[20]

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

[21]

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).

[22]

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

Digital Library

[23]

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

[24]

Alan Kuhnle. 2019. Interlaced Greedy Algorithm for Maximization of Submodular Functions in Nearly Linear Time. In Advances in Neural Information Processing Systems (NeurIPS).

[25]

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

[26]

Jure Leskovec and Andrej Krevl. 2020. SNAP Datasets: Stanford Large Network Dataset Collection. \url{http://snap.stanford.edu/data}.

[27]

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

[28]

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

[29]

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

[30]

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

[31]

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.

[32]

G L Nemhauser and L A Wolsey. 1978. Best Algorithms for Approximating the Maximum of a Submodular Set Function. Mathematics of Operations Research, Vol. 3, 3 (1978), 177--188. https://doi.org/10.1287/moor.3.3.177

Digital Library

[33]

G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher. 1978. An analysis of approximations for maximizing submodular set functions-I. Mathematical Programming, Vol. 14, 1 (1978), 265--294. https://doi.org/10.1007/BF01588971showDOI

Digital Library

Cited By

Wu YZhu ZMa CQian HLu XZhang YQin XFei BZhou JZhou ABaeza-Yates RBonchi F(2024)Cost-Efficient Fraud Risk Optimization with Submodularity in Insurance ClaimProceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3637528.3672012(3448-3459)Online publication date: 25-Aug-2024
https://dl.acm.org/doi/10.1145/3637528.3672012
Zhu YBasu SPavan ASerra ESpezzano F(2024)Regularized Unconstrained Weakly Submodular MaximizationProceedings of the 33rd ACM International Conference on Information and Knowledge Management10.1145/3627673.3679651(3537-3548)Online publication date: 21-Oct-2024
https://dl.acm.org/doi/10.1145/3627673.3679651
Pham C(2024)Enhanced deterministic approximation algorithm for non-monotone submodular maximization under knapsack constraint with linear query complexityJournal of Combinatorial Optimization10.1007/s10878-024-01232-949:1Online publication date: 22-Nov-2024
https://doi.org/10.1007/s10878-024-01232-9

Recommendations

Improved Deterministic Algorithms for Non-monotone Submodular Maximization
Computing and Combinatorics
Abstract
Submodular maximization is one of the central topics in combinatorial optimization. It has found numerous applications in the real world. In the past decades, a series of algorithms have been proposed for this problem. However, most of the state-...
Improved deterministic algorithms for non-monotone submodular maximization
Abstract
Submodular maximization is one of the central topics in combinatorial optimization. It has found numerous applications in the real world. In the past decades, a series of algorithms have been proposed for this problem. However, most of the state-...
Deterministic streaming algorithms for non-monotone submodular maximization
Abstract
Submodular maximization is a significant area of interest in combinatorial optimization. It has various real-world applications. In recent years, streaming algorithms for submodular maximization have gained attention, allowing realtime processing ...
$\frac{}{}$ $\frac{\overset{}{} \overset{}{}}{}$ $\frac{\overset{}{}}{}$ $\overset{}{}$ $\overset{}{}$

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

KDD '23: Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining

August 2023

5996 pages

ISBN:9798400701030

DOI:10.1145/3580305

General Chairs:
Ambuj Singh
UC Santa Barbara, USA
,
Yizhou Sun
UC Los Angeles, USA
,
Program Chairs:
Leman Akoglu
Carnegie Mellon University, USA
,
Dimitrios Gunopulos
University of Athens, Greece
,
Xifeng Yan
UC Santa Barbara, USA
,
Ravi Kumar
Google, USA
,
Fatma Ozcan
Google, USA
,
Jieping Ye
Alibaba DAMO Academy

Copyright © 2023 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 August 2023

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

KDD '23

Sponsor:

KDD '23: The 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining

August 6 - 10, 2023

CA, Long Beach, USA

Acceptance Rates

Overall Acceptance Rate 1,133 of 8,635 submissions, 13%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
518
Total Downloads

Downloads (Last 12 months)219
Downloads (Last 6 weeks)27

Reflects downloads up to 01 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Wu YZhu ZMa CQian HLu XZhang YQin XFei BZhou JZhou ABaeza-Yates RBonchi F(2024)Cost-Efficient Fraud Risk Optimization with Submodularity in Insurance ClaimProceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3637528.3672012(3448-3459)Online publication date: 25-Aug-2024
https://dl.acm.org/doi/10.1145/3637528.3672012
Zhu YBasu SPavan ASerra ESpezzano F(2024)Regularized Unconstrained Weakly Submodular MaximizationProceedings of the 33rd ACM International Conference on Information and Knowledge Management10.1145/3627673.3679651(3537-3548)Online publication date: 21-Oct-2024
https://dl.acm.org/doi/10.1145/3627673.3679651
Pham C(2024)Enhanced deterministic approximation algorithm for non-monotone submodular maximization under knapsack constraint with linear query complexityJournal of Combinatorial Optimization10.1007/s10878-024-01232-949:1Online publication date: 22-Nov-2024
https://doi.org/10.1007/s10878-024-01232-9

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Figures

Tables

Media

View Table of Conten