Document Open Access Logo

A Tight Approximation for Submodular Maximization with Mixed Packing and Covering Constraints

Authors Eyal Mizrachi, Roy Schwartz, Joachim Spoerhase , Sumedha Uniyal

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2019.85.pdf
  • Filesize: 0.57 MB
  • 15 pages

Document Identifiers

Author Details

Eyal Mizrachi
  • Computer Science Department, Technion, Haifa 32000, Israel
Roy Schwartz
  • Computer Science Department, Technion, Haifa 32000, Israel
Joachim Spoerhase
  • Department of Computer Science, Aalto University, Espoo, Finland
Sumedha Uniyal
  • Department of Computer Science, Aalto University, Espoo, Finland

Funding

  • Schwartz, Roy: Supported by ISF grant 1336/16 and NSF-BSF grant number 2016742.
  • Spoerhase, Joachim: Supported by European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant number 759557) and by Academy of Finland (grant number 310415).
  • Uniyal, Sumedha: Partially supported by Academy of Finland under the grant agreement number 314284.

Acknowledgements

Joachim Spoerhase and Sumedha Uniyal thank an anonymous reviewer for pointing them to the fact that Theorem 6 also applies to polytopes that are not down-closed, which makes it possible to apply a randomized rounding approach.

Cite As Get BibTex

Eyal Mizrachi, Roy Schwartz, Joachim Spoerhase, and Sumedha Uniyal. A Tight Approximation for Submodular Maximization with Mixed Packing and Covering Constraints. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 85:1-85:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ICALP.2019.85

Abstract

Motivated by applications in machine learning, such as subset selection and data summarization, we consider the problem of maximizing a monotone submodular function subject to mixed packing and covering constraints. We present a tight approximation algorithm that for any constant epsilon >0 achieves a guarantee of 1-(1/e)-epsilon while violating only the covering constraints by a multiplicative factor of 1-epsilon. Our algorithm is based on a novel enumeration method, which unlike previously known enumeration techniques, can handle both packing and covering constraints. We extend the above main result by additionally handling a matroid independence constraint as well as finding (approximate) pareto set optimal solutions when multiple submodular objectives are present. Finally, we propose a novel and purely combinatorial dynamic programming approach. While this approach does not give tight bounds it yields deterministic and in some special cases also considerably faster algorithms. For example, for the well-studied special case of only packing constraints (Kulik et al. [Math. Oper. Res. `13] and Chekuri et al. [FOCS `10]), we are able to present the first deterministic non-trivial approximation algorithm. We believe our new combinatorial approach might be of independent interest.

Subject Classification

ACM Subject Classification
  • Theory of computation → Submodular optimization and polymatroids
  • Theory of computation → Approximation algorithms analysis
Keywords
  • submodular function
  • approximation algorithm
  • covering
  • packing

Metrics

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

Related Versions

References

  1. A. A. Ageev and M. I. Sviridenko. An 0.828 Approximation Algorithm for the Uncapacitated Facility Location Problem. Discrete Appl. Math., 93(2-3):149-156, July 1999. Google Scholar
  2. Shabbir Ahmed and Alper Atamtürk. Maximizing a class of submodular utility functions. Mathematical Programming, 128(1):149-169, June 2011. Google Scholar
  3. Per Austrin, Siavosh Benabbas, and Konstantinos Georgiou. Better Balance by Being Biased: A 0.8776-Approximation for Max Bisection. ACM Trans. Algorithms, 13(1):2:1-2:27, 2016. Google Scholar
  4. Francis Bach. Learning with Submodular Functions: A Convex Optimization Perspective. Now Publishers Inc., Hanover, MA, USA, 2013. Google Scholar
  5. L. Bordeaux, Y. Hamadi, and P. Kohli. Tractability: Practical Approaches to Hard Problems. Cambridge University Press, 2014. Google Scholar
  6. Niv Buchbinder, Moran Feldman, Joseph Naor, and Roy Schwartz. Submodular Maximization with Cardinality Constraints. In Proc. 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'14), pages 1433-1452, 2014. Google Scholar
  7. Gruia Calinescu, 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, December 2011. Google Scholar
  8. Chandra Chekuri and Sanjeev Khanna. A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem. SIAM Journal on Computing, 35(3):713-728, 2005. Google Scholar
  9. Chandra Chekuri, Jan Vondrák, and Rico Zenklusen. Dependent Randomized Rounding via Exchange Properties of Combinatorial Structures. In Proc. 51th Annual IEEE Symposium on Foundations of Computer Science (FOCS'10), pages 575-584, 2010. Google Scholar
  10. Reuven Cohen, Liran Katzir, and Danny Raz. An Efficient Approximation for the Generalized Assignment Problem. Inf. Process. Lett., 100(4):162-166, November 2006. Google Scholar
  11. Gerard Cornuejols, Marshall Fisher, and George L. Nemhauser. On the Uncapacitated Location Problem. In Studies in Integer Programming, volume 1 of Annals of Discrete Mathematics, pages 163-177. Elsevier, 1977. Google Scholar
  12. Gerard Cornuejols, Marshall L. Fisher, and George L. Nemhauser. Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms. Management Science, 23(8):789-810, 1977. Google Scholar
  13. Shaddin Dughmi, Tim Roughgarden, and Mukund Sundararajan. Revenue Submodularity. Theory of Computing, 8(1):95-119, 2012. Google Scholar
  14. U. Feige and J. Vondrak. Approximation algorithms for allocation problems: Improving the factor of 1 - 1/e. In 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), pages 667-676, 2006. Google Scholar
  15. Uriel Feige. A Threshold of Ln N for Approximating Set Cover. J. ACM, 45(4):634-652, July 1998. Google Scholar
  16. Lisa Fleischer, Michel X Goemans, Vahab S Mirrokni, and Maxim Sviridenko. Tight approximation algorithms for maximum general assignment problems. In Proc. 17th annual ACM-SIAM Symposium on Discrete Algorithm, (SODA'06), pages 611-620. SIAM, 2006. Google Scholar
  17. Alan Frieze and Mark Jerrum. Improved approximation algorithms for MAX k-CUT and MAX BISECTION. In Egon Balas and Jens Clausen, editors, Integer Programming and Combinatorial Optimization, pages 1-13. Springer Berlin Heidelberg, 1995. Google Scholar
  18. J. Gillenwater. Approximate Inference for Determinantal Point Processes. PhD thesis, University of Pennsylvania, 2014. Google Scholar
  19. Jennifer Gillenwater, Alex Kulesza, and Ben Taskar. Near-Optimal MAP Inference for Determinantal Point Processes. In F. Pereira, C. J. C. Burges, L. Bottou, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems 25, pages 2735-2743. Curran Associates, Inc., 2012. Google Scholar
  20. Michel X. Goemans and David P. Williamson. Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming. J. ACM, 42(6):1115-1145, November 1995. Google Scholar
  21. Eran Halperin and Uri Zwick. Combinatorial Approximation Algorithms for the Maximum Directed Cut Problem. In Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '01, pages 1-7, 2001. Google Scholar
  22. Jason Hartline, Vahab Mirrokni, and Mukund Sundararajan. Optimal Marketing Strategies over Social Networks. In Proceedings of the 17th International Conference on World Wide Web, WWW '08, pages 189-198, 2008. Google Scholar
  23. Johan Håstad. Clique is hard to approximate within n^(1-ε). In Acta Mathematica, pages 627-636, 1996. Google Scholar
  24. Johan Håstad. Some Optimal Inapproximability Results. J. ACM, 48(4):798-859, July 2001. Google Scholar
  25. Xinran He and David Kempe. Stability of Influence Maximization. In Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '14, pages 1256-1265, 2014. Google Scholar
  26. Richard M. Karp. Reducibility among Combinatorial Problems, pages 85-103. Springer US, 1972. Google Scholar
  27. David Kempe, Jon Kleinberg, and Éva Tardos. Maximizing the Spread of Influence through a Social Network. Theory of Computing, 11(4):105-147, 2015. Google Scholar
  28. Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O'Donnell. Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs? SIAM Journal on Computing, 37(1):319-357, 2007. Google Scholar
  29. Samir Khuller, Anna Moss, and Joseph Seffi Naor. The budgeted maximum coverage problem. Information Processing Letters, 70(1):39-45, 1999. Google Scholar
  30. Alex Kulesza and Ben Taskar. Learning Determinantal Point Processes. In UAI 2011, Proceedings of the Twenty-Seventh Conference on Uncertainty in Artificial Intelligence, Barcelona, Spain, July 14-17, 2011, pages 419-427, 2011. Google Scholar
  31. Alex Kulesza and Ben Taskar. Determinantal Point Processes for Machine Learning. Foundations and Trends in Machine Learning, 5(2-3):123-286, 2012. Google Scholar
  32. 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. preliminary version appeared in SODA'09. Google Scholar
  33. Jon Lee, Vahab S Mirrokni, Viswanath Nagarajan, and Maxim Sviridenko. Non-monotone submodular maximization under matroid and knapsack constraints. In Proc. 41st Annual ACM Symposium on Theory Of Computing, (STOC'09), pages 323-332. ACM, 2009. Google Scholar
  34. Hui Lin and Jeff Bilmes. Multi-document Summarization via Budgeted Maximization of Submodular Functions. In Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics, HLT '10, pages 912-920, 2010. Google Scholar
  35. Hui Lin and Jeff Bilmes. A Class of Submodular Functions for Document Summarization. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies - Volume 1, HLT '11, pages 510-520, 2011. Google Scholar
  36. Eyal Mizrachi, Roy Schwartz, Joachim Spoerhase, and Sumedha Uniyal. A Tight Approximation for Submodular Maximization with Mixed Packing and Covering Constraints. CoRR, abs/1804.10947, 2018. URL: http://arxiv.org/abs/1804.10947.
  37. 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. Google Scholar
  38. George L Nemhauser and Leonard A Wolsey. Best algorithms for approximating the maximum of a submodular set function. Mathematics of operations research, 3(3):177-188, 1978. Google Scholar
  39. Andreas S. Schulz and Nelson A. Uhan. Approximating the least core value and least core of cooperative games with supermodular costs. Discrete Optimization, 10(2):163-180, 2013. Google Scholar
  40. Maxim Sviridenko. A note on maximizing a submodular set function subject to a knapsack constraint. Oper. Res. Lett., 32(1):41-43, 2004. Google Scholar
  41. Jan Vondrák. Symmetry and Approximability of Submodular Maximization Problems. In Proc. 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS'09), pages 651-670. IEEE, 2009. Google Scholar
  42. 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
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