Document Open Access Logo

A Nearly-Linear Time Algorithm for Submodular Maximization with a Knapsack Constraint

Authors Alina Ene, Huy L. Nguyen

PDF

File

Thumbnail PDF
PDF
LIPIcs.ICALP.2019.53.pdf
  • Filesize: 0.52 MB
  • 12 pages

Document Identifiers

Related Versions

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)
    0
    PDF Downloads
    0
    Metadata Views

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.

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

Author Details

Alina Ene
  • Department of Computer Science, Boston University, MA, USA
Huy L. Nguyen
  • College of Computer and Information Science, Northeastern University, Boston, MA, USA

Funding

  • Ene, Alina: Partially supported by NSF CAREER grant CCF-1750333 and NSF grant CCF-1718342.
  • Nguyen, Huy L.: Partially supported by NSF CAREER grant CCF-1750716.

Acknowledgements

This work was done in part while the authors were visiting the Simons Institute for the Theory of Computing.

References

  1. Ashwinkumar Badanidiyuru and Jan Vondrák. Fast algorithms for maximizing submodular functions. In ACM-SIAM Symposium on Discrete Algorithms (SODA), 2014. Google Scholar
  2. Shaddin Dughmi, Tim Roughgarden, and Mukund Sundararajan. Revenue Submodularity. Theory of Computing, 8(1):95-119, 2012. Google Scholar
  3. Ryan Gomes and Andreas Krause. Budgeted Nonparametric Learning from Data Streams. In International Conference on Machine Learning (ICML), pages 391-398, 2010. Google Scholar
  4. 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. Google Scholar
  5. 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. Google Scholar
  6. Samir Khuller, Anna Moss, and Joseph Seffi Naor. The budgeted maximum coverage problem. Information processing letters, 70(1):39-45, 1999. Google Scholar
  7. 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. Google Scholar
  8. 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. Google Scholar
  9. 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. Google Scholar
  10. Maxim Sviridenko. A note on maximizing a submodular set function subject to a knapsack constraint. Operations Research Letters, 32(1):41-43, 2004. Google Scholar
  11. Laurence A Wolsey. Maximising real-valued submodular functions: Primal and dual heuristics for location problems. Mathematics of Operations Research, 7(3):410-425, 1982. Google Scholar
  12. 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.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact