Maximizing submodular set functions subject to multiple linear constraints

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Maximizing submodular set functions subject to multiple linear constraints

Full text

Pdf (508 KB)

Source

Symposium on Discrete Algorithms archive
Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms table of contents

New York, New York

Pages 545-554

Year of Publication: 2009

Authors

Ariel Kulik	Technion, Haifa, Israel
Hadas Shachnai	Technion, Haifa, Israel
Tami Tamir	The Interdisciplinary Center, Herzliya, Israel

Publisher

Society for Industrial and Applied Mathematics Philadelphia, PA, USA

Bibliometrics

Downloads (6 Weeks): 10, Downloads (12 Months): 87, Citation Count: 1

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

ABSTRACT

The concept of submodularity plays a vital role in combinatorial optimization. In particular, many important optimization problems can be cast as submodular maximization problems, including maximum coverage, maximum facility location and max cut in directed/undirected graphs.

In this paper we present the first known approximation algorithms for the problem of maximizing a nondecreasing submodular set function subject to multiple linear constraints. Given a d-dimensional budget vector [EQUATION], for some d ≥ 1, and an oracle for a non-decreasing submodular set function f over a universe U, where each element e ∈ U is associated with a d-dimensional cost vector, we seek a subset of elements S ⊆ U whose total cost is at most [EQUATION], such that f(S) is maximized.

We develop a framework for maximizing submodular functions subject to d linear constraints that yields a (1 - ε)(1 - e⁻¹)-approximation to the optimum for any ε > 0, where d > 1 is some constant. Our study is motivated by a variant of the classical maximum coverage problem that we call maximum coverage with multiple packing constraints. We use our framework to obtain the same approximation ratio for this problem. To the best of our knowledge, this is the first time the theoretical bound of 1 - e⁻¹ is (almost) matched for both of these problems.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	A. Ageev and M. Sviridenko. Pipage rounding: A new method of constructing algorithms with proven performance guarantee. J. Combinatorial Optimization, 8(3):307--328, 2004.
	2	Gruia Calinescu , Chandra Chekuri , Martin Pál , Jan Vondrák, Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract), Proceedings of the 12th international conference on Integer Programming and Combinatorial Optimization, June 25-27, 2007, Ithaca, NY, USA [doi>10.1007/978-3-540-72792-7_15]
	3	C. Chekuri and A. Kumar. Maximum coverage problem with group budget constraints and applications. In APPROX-RANDOM, pages 72--83, 2004.
	4	Uriel Feige, A threshold of ln n for approximating set cover, Journal of the ACM (JACM), v.45 n.4, p.634-652, July 1998 [doi>10.1145/285055.285059]
	5	Uriel Feige , Vahab S. Mirrokni , Jan Vondrak, Maximizing Non-Monotone Submodular Functions, Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, p.461-471, October 21-23, 2007 [doi>10.1109/FOCS.2007.40]
	6	A. M. Frieze and M. Clarke. Approximation algorithms for the m-dimensional 0--1 knapsack problem: worstcase and probabilistic analyses. European J. of Operational Research, 15(1):100--109, 1984.
	7	T. Fujito. Approximation algorithms for submodular set cover with applications. IEICE Trans. Inf. and Systems, E83--D(3), 2000.
	8	H. Kellerer, U. Pferschy, and D. Pisinger. Knapsack Problems. Springer, 1 edition, October 2004.
	9	Samir Khuller , Anna Moss , Joseph (Seffi) Naor, The budgeted maximum coverage problem, Information Processing Letters, v.70 n.1, p.39-45, April 01, 1999 [doi>10.1016/S0020-0190(99)00031-9]
	10	A. Kulik, H. Shachnai, and T. Tamir. Maximizing submodular set functions subject to multiple linear constraints. full version. http://www.cs.technion.ac.il/~hadas/PUB/max_submodular.pdf.
	11	G. Nemhauser, L. Wolsey, and M. Fisher. An analysis of the approximations for maximizing submodular set functions. Mathematical Programming, 14:265--294, 1978.
	12	A. Schriejver. Combinatorial Optimization - polyhedra and efficiency. Springer Verlag - Berlin Heidelberg, 2003.
	13	H. Shachnai and T. Tamir. Polynomial time approximation schemes for class-constrained packing problems. J. of Scheduling, 4(6):313--338, 2001.
	14	A. Srinivasan, Distributions on Level-Sets with Applications to Approximation Algorithms, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.588, October 14-17, 2001
	15	M. Sviridenko. A note on maximizing a submodular set function subject to knapsack constraint. Operations Research Letters, 32:41--43, 2004.
	16	Jan Vondrak, Optimal approximation for the submodular welfare problem in the value oracle model, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374389]