Document Open Access Logo

Maximizing a Submodular Function with Bounded Curvature Under an Unknown Knapsack Constraint

Authors Max Klimm, Martin Knaack

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2022.49.pdf
  • Filesize: 0.73 MB
  • 19 pages

Document Identifiers

Author Details

Max Klimm
  • Institute for Mathematics, Technische Universität Berlin, Germany
Martin Knaack
  • Institute for Mathematics, Technische Universität Berlin, Germany

Acknowledgements

The authors wish to thank Daniel Schmidt genannt Waldschmidt for fruitful discussion.

Cite As Get BibTex

Max Klimm and Martin Knaack. Maximizing a Submodular Function with Bounded Curvature Under an Unknown Knapsack Constraint. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 49:1-49:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2022.49

Abstract

This paper studies the problem of maximizing a monotone submodular function under an unknown knapsack constraint. A solution to this problem is a policy that decides which item to pack next based on the past packing history. The robustness factor of a policy is the worst case ratio of the solution obtained by following the policy and an optimal solution that knows the knapsack capacity. We develop an algorithm with a robustness factor that is decreasing in the curvature c of the submodular function. For the extreme cases c = 0 corresponding to a modular objective, it matches a previously known and best possible robustness factor of 1/2. For the other extreme case of c = 1 it yields a robustness factor of ≈ 0.35 improving over the best previously known robustness factor of ≈ 0.06.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Submodular optimization and polymatroids
  • Theory of computation → Packing and covering problems
  • Theory of computation → Online algorithms
Keywords
  • submodular function
  • knapsack
  • approximation algorithm
  • robust optimization

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Aaron Bernstein, Yann Disser, Martin Groß, and Sandra Himburg. General bounds for incremental maximization. Math. Program., 2020. URL: https://doi.org/10.1007/s10107-020-01576-0.
  2. Gruia Călinescu, Chandra Chekuri, Martin Pál, and Jan Vondrák. Maximizing a monotone submodular function subject to a matroid constraint. SIAM J. Comput., 40(6):1740-1766, 2011. URL: https://doi.org/10.1137/080733991.
  3. Michele Conforti and Gérard Cornuéjols. Submodular set functions, matroids and the greedy algorithm: Tight worst-case bounds and some generalizations of the Rado-Edmonds theorem. Discret. Appl. Math., 7(3):251-274, 1984. URL: https://doi.org/10.1016/0166-218X(84)90003-9.
  4. Gerard Cornuéjols, Marshall L. Fisher, and George L. Nemhauser. Location of bank accounts to optimize float: An analytic study of exact and approximate algorithms. Management Sci., 23:789-810, 1977. URL: https://doi.org/10.1287/mnsc.23.8.789.
  5. Yann Disser, Max Klimm, Nicole Megow, and Sebastian Stiller. Packing a knapsack of unknown capacity. SIAM J. Discret. Math., 31(3):1477-1497, 2017. URL: https://doi.org/10.1137/16M1070049.
  6. Yann Disser, Max Klimm, and David Weckbecker. Fractionally subadditive maximization under an incremental knapsack constraint. In Jochen Könemann and Britta Peis, editors, Approximation and Online Algorithms - 19th International Workshop (WAOA), volume 12982 of Lecture Notes in Computer Science, pages 206-223. Springer, 2021. URL: https://doi.org/10.1007/978-3-030-92702-8_13.
  7. Uriel Feige. A threshold of ln n for approximating set cover. J. ACM, 45(4):634-652, 1998. URL: https://doi.org/10.1145/285055.285059.
  8. Marshall L. Fisher, George L. Nemhauser, and Laurence A. Wolsey. An analysis of approximations for maximizing submodular set functions - II, volume 8 of Mathematical Programming Studies, page 73–87. Springer, Berlin, Heidelberg, 1978. URL: https://doi.org/10.1007/BFb0121195.
  9. Yasushi Kawase, Hanna Sumita, and Takuro Fukunaga. Submodular maximization with uncertain knapsack capacity. SIAM J. Discret. Math., 33(3):1121-1145, 2019. URL: https://doi.org/10.1137/18M1174428.
  10. David Kempe, Jon M. Kleinberg, and Éva Tardos. Maximizing the spread of influence through a social network. Theory Comput., 11:105-147, 2015. URL: https://doi.org/10.4086/toc.2015.v011a004.
  11. Bernhard Korte and Jens Vygen. Combinatorial Optimization. Springer, Heidelberg, Berlin, 2018. Google Scholar
  12. Andreas Krause and Carlos Guestrin. Submodularity and its applications in optimized information gathering. ACM Trans. Intell. Syst. Technol., 2(4):32:1-32:20, 2011. URL: https://doi.org/10.1145/1989734.1989736.
  13. Andreas Krause, Ajit Paul Singh, and Carlos Guestrin. Near-optimal sensor placements in gaussian processes: Theory, efficient algorithms and empirical studies. J. Mach. Learn. Res., 9:235-284, 2008. URL: https://dl.acm.org/citation.cfm?id=1390689.
  14. Jon Lee. Constrained maximum-entropy sampling. Oper. Res., 46(5):655-664, 1998. URL: https://doi.org/10.1287/opre.46.5.655.
  15. Nicole Megow and Julián Mestre. Instance-sensitive robustness guarantees for sequencing with unknown packing and covering constraints. In Robert D. Kleinberg, editor, Innovations in Theoretical Computer Science (ITCS), pages 495-504. ACM, 2013. URL: https://doi.org/10.1145/2422436.2422490.
  16. Alfredo Navarra and Cristina M. Pinotti. Online knapsack of unknown capacity: How to optimize energy consumption in smartphones. Theor. Comput. Sci., 697:98-109, 2017. URL: https://doi.org/10.1016/j.tcs.2017.07.029.
  17. George L. Nemhauser and Laurence A. Wolsey. Best algorithms for approximating the maximum of a submodular set function. Math. Oper. Res., 3(3):177-188, 1978. URL: https://doi.org/10.1287/moor.3.3.177.
  18. George L. Nemhauser, Laurence A. Wolsey, and Marshall L. Fisher. An analysis of approximations for maximizing submodular set functions - I. Math. Program., 14(1):265-294, 1978. URL: https://doi.org/10.1007/BF01588971.
  19. Maxim Sviridenko. A note on maximizing a submodular set function subject to a knapsack constraint. Oper. Res. Lett., 32(1):41-43, 2004. URL: https://doi.org/10.1016/S0167-6377(03)00062-2.
  20. Maxim Sviridenko, Jan Vondrák, and Justin Ward. Optimal approximation for submodular and supermodular optimization with bounded curvature. Math. Oper. Res., 42(4):1197-1218, 2017. URL: https://doi.org/10.1287/moor.2016.0842.
  21. Jan Vondrák. Submodularity and curvature: The optimal algorithm. RIMS Kôkyûroku Bessatsu, B23:253-266, 2010. Google Scholar
  22. Laurence A. Wolsey. Maximising real-valued submodular functions: Primal and dual heuristics for location problems. Math. Oper. Res., 7(3):410-425, 1982. URL: https://doi.org/10.1287/moor.7.3.410.
  23. Yuichi Yoshida. Maximizing a monotone submodular function with a bounded curvature under a knapsack constraint. SIAM J. Discret. Math., 33(3):1452-1471, 2019. URL: https://doi.org/10.1137/16M1107644.
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-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact