LIPIcs.ICALP.2019.53.pdf
- Filesize: 0.52 MB
- 12 pages
Document
A Nearly-Linear Time Algorithm for Submodular Maximization with a Knapsack Constraint
Authors
-
Part of:
Volume:
46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Colloquium on Automata, Languages, and Programming (ICALP) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2019-07-04
File
Document Identifiers
Acknowledgements
This work was done in part while the authors were visiting the Simons Institute for the Theory of Computing.
Cite As Get BibTex
Alina Ene and Huy L. Nguyen. A Nearly-Linear Time Algorithm for Submodular Maximization with a Knapsack Constraint. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 53:1-53:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ICALP.2019.53
Abstract
We consider the problem of maximizing a monotone submodular function subject to a knapsack constraint. Our main contribution is an algorithm that achieves a nearly-optimal, 1 - 1/e - epsilon approximation, using (1/epsilon)^{O(1/epsilon^4)} n log^2{n} function evaluations and arithmetic operations. Our algorithm is impractical but theoretically interesting, since it overcomes a fundamental running time bottleneck of the multilinear extension relaxation framework. This is the main approach for obtaining nearly-optimal approximation guarantees for important classes of constraints but it leads to Omega(n^2) running times, since evaluating the multilinear extension is expensive. Our algorithm maintains a fractional solution with only a constant number of entries that are strictly fractional, which allows us to overcome this obstacle.
Subject Classification
ACM Subject Classification
- Theory of computation → Submodular optimization and polymatroids
Keywords
- submodular maximization
- knapsack constraint
- fast algorithms
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Ashwinkumar Badanidiyuru and Jan Vondrák. Fast algorithms for maximizing submodular functions. In ACM-SIAM Symposium on Discrete Algorithms (SODA), 2014.
-
Shaddin Dughmi, Tim Roughgarden, and Mukund Sundararajan. Revenue Submodularity. Theory of Computing, 8(1):95-119, 2012.
-
Ryan Gomes and Andreas Krause. Budgeted Nonparametric Learning from Data Streams. In International Conference on Machine Learning (ICML), pages 391-398, 2010.
-
Stefanie Jegelka and Jeff A. Bilmes. Submodularity beyond submodular energies: Coupling edges in graph cuts. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2011.
-
David Kempe, Jon M. Kleinberg, and Éva Tardos. Maximizing the spread of influence through a social network. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pages 137-146, 2003.
-
Samir Khuller, Anna Moss, and Joseph Seffi Naor. The budgeted maximum coverage problem. Information processing letters, 70(1):39-45, 1999.
-
Andreas Krause, Ajit Paul Singh, and Carlos Guestrin. Near-Optimal Sensor Placements in Gaussian Processes: Theory, Efficient Algorithms and Empirical Studies. Journal of Machine Learning Research, 9:235-284, 2008.
-
Ariel Kulik, Hadas Shachnai, and Tami Tamir. Approximations for monotone and nonmonotone submodular maximization with knapsack constraints. Mathematics of Operations Research, 38(4):729-739, 2013.
-
Hui Lin and Jeff A. Bilmes. Multi-document Summarization via Budgeted Maximization of Submodular Functions. In Human Language Technologies: Conference of the North American Chapter of the Association of Computational Linguistics, pages 912-920, 2010.
-
Maxim Sviridenko. A note on maximizing a submodular set function subject to a knapsack constraint. Operations Research Letters, 32(1):41-43, 2004.
-
Laurence A Wolsey. Maximising real-valued submodular functions: Primal and dual heuristics for location problems. Mathematics of Operations Research, 7(3):410-425, 1982.
- Yuichi Yoshida. Maximizing a Monotone Submodular Function with a Bounded Curvature under a Knapsack Constraint. CoRR, abs/1607.04527, 2016. URL: http://arxiv.org/abs/1607.04527.