Non-monotone submodular maximization under matroid and knapsack constraints

ABSTRACT

Submodular function maximization is a central problem in combinatorial optimization, generalizing many important problems including Max Cut in directed/undirected graphs and in hypergraphs, certain constraint satisfaction problems, maximum entropy sampling, and maximum facility location problems. Unlike submodular minimization, submodular maximization is NP-hard. In this paper, we give the first constant-factor approximation algorithm for maximizing any non-negative submodular function subject to multiple matroid or knapsack constraints. We emphasize that our results are for non-monotone submodular functions. In particular, for any constant k, we present a (1/k+2+1/k+ε)-approximation for the submodular maximization problem under k matroid constraints, and a (1/5-ε)-approximation algorithm for this problem subject to k knapsack constraints (ε>0 is any constant). We improve the approximation guarantee of our algorithm to 1/k+1+{1/k-1}+ε for k≥2 partition matroid constraints. This idea also gives a ({1/k+ε)-approximation for maximizing a monotone submodular function subject to k≥2 partition matroids, which improves over the previously best known guarantee of 1/k+1.

REFERENCES

• 1: Alexander Ageev , Refael Hassin , Maxim Sviridenko, A 0.5-Approximation Algorithm for MAX DICUT with Given Sizes of Parts, SIAM Journal on Discrete Mathematics, v.14 n.2, p.246-255, 2001 [doi>10.1137/S089548010036813X]
• 2: A. A. Ageev , M. I. Sviridenko, An 0.828–approximation algorithm for the uncapacitated facility location problem, Discrete Applied Mathematics, v.93 n.2-3, p.149-156, July 20, 1999 [doi>10.1016/S0166-218X(99)00103-1]
• 3: . Ageev and M. Sviridenko, Pipage rounding: a new method ofconstructing algorithms with proven performance guarantee. J. Comb. Optim. 8 (2004), no. 3, 307--328.
• 4: Paola Alimonti, Non-oblivious Local Search for MAX 2-CCSP with Application to MAX DICUT, Proceedings of the 23rd International Workshop on Graph-Theoretic Concepts in Computer Science, p.2-14, June 18-20, 1997
• 5: K. M. Anstreicher, M. Fampa, J. Lee and J.Williams. Using continuous nonlinear relaxations to solve constrained maximum--entropy sampling problems. Mathematical Programming, Series A, 85:221--240, 1999.
• 6: Samuel Burer , Jon Lee, Solving maximum-entropy sampling problems using factored masks, Mathematical Programming: Series A and B, v.109 n.2, p.263-281, January 2007 [doi>10.1007/s10107-006-0024-1]
• 7: . Calinescu, C. Chekuri, M. Pál and J. Vondrák. Maximizing a monotone submodular function under a matroid constraint, IPCO 2007.
• 8: . Cherenin. Solving some combinatorial problems of optimal planning by the method of successive calculations, Proc. of the Conference of Experiences and Perspectives of the Applications of Mathematical Methods and Electronic Computers in Planning (in Russian), Mimeograph,Novosibirsk (1962).
• 9: . Cornuéjols, M. Fischer and G. Nemhauser. Location of bank accounts to optimize oat: An analytic study of exact and approximation algorithms, Management Science, 23 (1977), 789--810.
• 10: . Cornuéjols, M. Fischer and G. Nemhauser. On the uncapacitated location problem, Annals of Discrete Math 1 (1977), 163--178.
• 11: . P. Cornuéjols, G. L. Nemhauser and L. A. Wolsey.The uncapacitated facility location problem. In Discrete Location Theory (1990), 119--171.
• 12: . Edmonds. Matroids, submodular functions, and certain polyhedra, Combinatorial Structures and Their Applications (1970), 69--87.
• 13: 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]
• 14: Approximating the value of two power proof systems, with applications to MAX 2SAT and MAX DICUT, Proceedings of the 3rd Israel Symposium on the Theory of Computing Systems (ISTCS'95), p.182, January 04-06, 1995
• 15: 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]
• 16: . Frank. Matroids and submodular functions, Annotated Biblographies in Combinatorial Optimization (1997), 65--80.
• 17: . Fujishige. Canonical decompositions of symmetric submodular systems, Discrete Applied Mathematics 5 (1983), 175--190.
• 18: Michel X. Goemans , Nicholas J. A. Harvey , Satoru Iwata , Vahab Mirrokni, Approximating submodular functions everywhere, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.535-544, January 04-06, 2009, New York, New York
• 19: Michel X. Goemans , David P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the ACM (JACM), v.42 n.6, p.1115-1145, Nov. 1995 [doi>10.1145/227683.227684]
• 20: Boris Goldengorin , Gerard Sierksma , Gert A. Tijssen , Michael Tso, The Data-Correcting Algorithm for the Minimization of Supermodular Functions, Management Science, v.45 n.11, p.1539-1551, November 1999 [doi>10.1287/mnsc.45.11.1539]
• 21: . Goldengorin, G. Tijsssen and M. Tso.The maximization of submodular Functions: Old and new proofs for the correctness of the dichotomy algorithm, SOM Report, University of Groningen (1999).
• 22: Eran Halperin , Uri Zwick, Combinatorial approximation algorithms for the maximum directed cut problem, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.1-7, January 07-09, 2001, Washington, D.C., United States
• 23: Jason Hartline , Vahab Mirrokni , Mukund Sundararajan, Optimal marketing strategies over social networks, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China [doi>10.1145/1367497.1367524]
• 24: Elad Hazan , Shmuel Safra , Oded Schwartz, On the complexity of approximating k-set packing, Computational Complexity, v.15 n.1, p.20-39, May 2006 [doi>10.1007/s00037-006-0205-6]
• 25: Johan Håstad, Some optimal inapproximability results, Journal of the ACM (JACM), v.48 n.4, p.798-859, July 2001 [doi>10.1145/502090.502098]
• 26: Satoru Iwata , Lisa Fleischer , Satoru Fujishige, A combinatorial strongly polynomial algorithm for minimizing submodular functions, Journal of the ACM (JACM), v.48 n.4, p.761-777, July 2001 [doi>10.1145/502090.502096]
• 27: . R. Khachaturov, Mathematical Methods of Regional Programming, Nauka, Moscow (in Russian), 1989.
• 28: Ariel Kulik , Hadas Shachnai , Tami Tamir, Maximizing submodular set functions subject to multiple linear constraints, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.545-554, January 04-06, 2009, New York, New York
• 29: C.-W. Ko, J. Lee and M. Queyranne. An exactalgorithm for maximum entropy sampling. Operations Research 43(4):684--691, 1995.
• 30: Andreas Krause , Ajit Singh , Carlos Guestrin, Near-Optimal Sensor Placements in Gaussian Processes: Theory, Efficient Algorithms and Empirical Studies, The Journal of Machine Learning Research, 9, p.235-284, 6/1/2008
• 31: . Lee, G. Nemhauser and Y. Wang.Maximizing a submodular function by integer programming: Polyhedral results for the quadratic case, European Journal of Operational Research 94, 154--166.
• 32: J. Lee. Maximum entropy sampling. In: A.H. El-Shaarawi and W.W. Piegorsch, editors, "Encyclopedia of Environmetrics". Wiley, 2001.
• 33: J. Lee. Semidefinite programming in experimental design.In: H. Wolkowicz, R. Saigal and L. Vandenberghe, editors, "Handbook of Semidefinite Programming", International Series in Operations Research and Management Science, Vol. 27, Kluwer, 2000.
• 34: Jon Lee, Constrained Maximum-Entropy Sampling, Operations Research, v.46 n.5, p.655-664, May 1998 [doi>10.1287/opre.46.5.655]
• 35: . Lee, V. Mirrokni, V. Nagarajan and M. Sviridenko. Maximizing Non-Monotone Submodular Functions under Matroid and Knapsack Constraints. IBM Research Report RC24679, 2008.
• 36: . Lovász. Submodular functions and convexity. In: A. Bachem et. al., eds, "Mathematical Programmming: The State of the Art," 235--257.
• 37: Vahab Mirrokni , Michael Schapira , Jan Vondrak, Tight information-theoretic lower bounds for welfare maximization in combinatorial auctions, Proceedings of the 9th ACM conference on Electronic commerce, July 08-12, 2008, Chicago, Il, USA [doi>10.1145/1386790.1386805]
• 38: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 39: . L. Nemhauser, L. A. Wolsey and M. L. Fisher. An analysis of approximations for maximizing submodular set functions I. Mathematical Programming 14 (1978), 265--294.
• 40: . L. Nemhauser, L. A. Wolsey and M. L. Fisher. An analysis of approximations for maximizing submodular set functions II. Mathematical Programming Study 8 (1978), 73--87.
• 41: . G. Oxley,"Matroid theory," Oxford Science Publications. The Clarendon Press, Oxford University Press, New York, 1992.
• 42: Maurice Queyranne, A combinatorial algorithm for minimizing symmetric submodular functions, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.98-101, January 22-24, 1995, San Francisco, California, United States
• 43: Joachim Reichel , Martin Skutella, Evolutionary algorithms and matroid optimization problems, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1277149]
• 44: T. G. Robertazzi , S. C. Schwartz, An accelerated sequential algorithm for producing D-optimal designs, SIAM Journal on Scientific and Statistical Computing, v.10 n.2, p.341-358, March 1989 [doi>10.1137/0910022]
• 45: Alexander Schrijver, A combinatorial algorithm minimizing submodular functions in strongly polynomial time, Journal of Combinatorial Theory Series B, v.80 n.2, p.346-355, Nov. 2000 [doi>10.1006/jctb.2000.1989]
• 46: . Schrijver. "Combinatorial Optimization," Volumes A-C. Springer-Verlag, Berlin, 2003.
• 47: Andreas S. Schulz , Nelson A. Uhan, Encouraging Cooperation in Sharing Supermodular Costs, Proceedings of the 10th International Workshop on Approximation and the 11th International Workshop on Randomization, and Combinatorial Optimization. Algorithms and Techniques, August 20-22, 2007, Princeton, NJ, USA [doi>10.1007/978-3-540-74208-1_20]
• 48: . C. Shewry, H. P. Wynn, Maximum entropy sampling. J. Appl. Stat. 14 (1987), 165--170.
• 49: . Sviridenko. A note on maximizing a submodular set function subject to knapsack constraint. Operations Research Letters 32 (2004), 41--43.
• 50: Zoya Svitkina , Lisa Fleischer, Submodular Approximation: Sampling-based Algorithms and Lower Bounds, Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science, p.697-706, October 25-28, 2008 [doi>10.1109/FOCS.2008.66]
• 51: 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]
• 52: . Vondrák, Personal communication, 2008.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms, Theory

Keywords:
approximation algorithms, knapsacks, matroids, submodular functions