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.
- . Ageev, R. Hassin and M. Sviridenko, An 0.5-approximation algorithm for MAX DICUT with given sizes of parts. SIAM J. Discrete Math. 14 (2001), no. 2, 246--255 (electronic). Google ScholarDigital Library
- . Ageev and M. Sviridenko. An 0.828 Approximation algorithm for the uncapacitated facility location problem, phDiscrete Applied Mathematics 93(2--3): 149--156 (1999). Google ScholarDigital Library
- . Ageev and M. Sviridenko, Pipage rounding: a new method ofconstructing algorithms with proven performance guarantee. J. Comb. Optim. 8 (2004), no. 3, 307--328.Google Scholar
- . Alimonti. Non-oblivious local search for MAX 2-CCSP withapplication to MAX DICUT, In Proceedings of the 23rd International Workshop on Graph-theoretic Concepts in Computer Science, 1997. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- . Burer and J. Lee. Solving maximum-entropysampling problems using factored masks. Mathematical Programming, Volume 109, Numbers 2--3, 263--281, 2007Google Scholar
- . Calinescu, C. Chekuri, M. Pál and J. Vondrák. Maximizing a monotone submodular function under a matroid constraint, IPCO 2007.Google Scholar
- . 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).Google Scholar
- . 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.Google ScholarDigital Library
- . Cornuéjols, M. Fischer and G. Nemhauser. On the uncapacitated location problem, Annals of Discrete Math 1 (1977), 163--178.Google ScholarCross Ref
- . P. Cornuéjols, G. L. Nemhauser and L. A. Wolsey.The uncapacitated facility location problem. In Discrete Location Theory (1990), 119--171.Google Scholar
- . Edmonds. Matroids, submodular functions, and certain polyhedra, Combinatorial Structures and Their Applications (1970), 69--87.Google Scholar
- . Feige. A threshold of łn n for approximating set cover. Journal of ACM 45 (1998), 634--652. Google ScholarDigital Library
- . Feige and M. X. Goemans. Approximating the value of two-prover systems, with applications to MAX-2SAT and MAX-DICUT. Proc. of the 3rd Israel Symposium on Theory and Computing Systems, Tel Aviv (1995), 182--189. Google ScholarDigital Library
- . Feige, V. Mirrokni and J. Vondrák. Maximizing non-monotone submodular functions, FOCS 2007. Google ScholarDigital Library
- . Frank. Matroids and submodular functions, Annotated Biblographies in Combinatorial Optimization (1997), 65--80.Google Scholar
- . Fujishige. Canonical decompositions of symmetric submodular systems, Discrete Applied Mathematics 5 (1983), 175--190.Google ScholarCross Ref
- M. Goemans, N. Harvey, S. Iwata, V. Mirrokni. Approximating submodular functions everywhere. In SODA 2009. Google ScholarDigital Library
- . X. Goemans and D. P. Williamson.Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of ACM 42 (1995), 1115--1145. Google ScholarDigital Library
- . Goldengorin, G. Sierksma, G. Tijsssen and M. Tso. The data correcting algorithm for the minimization of supermodular functions, Management Science, 45:11 (1999), 1539--1551. Google ScholarDigital Library
- . 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).Google Scholar
- . Halperin and U. Zwick. Combinatorial approximation algorithms for the maximum directed cut problem. Proc. of 12th SODA (2001), 1--7. Google ScholarDigital Library
- J. Hartline, V. Mirrokni and M. Sundararajan. Optimal marketing strategies over social networks, World Wide Web Conference (WWW), 2008, 189--198. Google ScholarDigital Library
- . Hazan, S. Safra and O. Schwartz. On the complexityof approximating k-set packing. Computational Complexity, 15(1), 20--39, 2006. Google ScholarDigital Library
- . Håstad. Some optimal inapproximability results. Journal of ACM 48 (2001): 798--869. Google ScholarDigital Library
- S. Iwata, L. Fleischer and S. Fujishige. A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions, Journal of ACM 48:4 (2001), 761--777. Google ScholarDigital Library
- . R. Khachaturov, Mathematical Methods of Regional Programming, Nauka, Moscow (in Russian), 1989.Google Scholar
- . Kulik, H. Shachnai and T. Tamir. Maximizing submodular functionssubject to multiple linear constraints. Proc. of SODA, 2009. Google ScholarDigital Library
- C.-W. Ko, J. Lee and M. Queyranne. An exactalgorithm for maximum entropy sampling. Operations Research 43(4):684--691, 1995.Google ScholarDigital Library
- . Krause, A. Singh and C. Guestrin.Near-optimal sensor placements in Gaussian processes: Theory, efficient algorithms and empirical studies, Journal of Machine Learning Research 9 (2008) 235--284. Google ScholarDigital Library
- . 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.Google Scholar
- J. Lee. Maximum entropy sampling. In: A.H. El-Shaarawi and W.W. Piegorsch, editors, "Encyclopedia of Environmetrics". Wiley, 2001.Google Scholar
- 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.Google Scholar
- J. Lee. Constrained maximum-entropy sampling.phOperations Research, 46:655--664, 1998. Google ScholarDigital Library
- . Lee, V. Mirrokni, V. Nagarajan and M. Sviridenko. Maximizing Non-Monotone Submodular Functions under Matroid and Knapsack Constraints. IBM Research Report RC24679, 2008.Google Scholar
- . Lovász. Submodular functions and convexity. In: A. Bachem et. al., eds, "Mathematical Programmming: The State of the Art," 235--257.Google Scholar
- . Mirrokni, J. Vondrák and M. Schapira. Tight Information-Theoretic Lower Bounds for Welfare Maximization in Combinatorial Auctions. Proc. of EC, 2008, 70--77. Google ScholarDigital Library
- . Motwani and P. Raghavan. Randomized Algorithms,Cambridge University Press, 1995. Google ScholarDigital Library
- . 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.Google ScholarDigital Library
- . 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.Google ScholarCross Ref
- . G. Oxley,"Matroid theory," Oxford Science Publications. The Clarendon Press, Oxford University Press, New York, 1992.Google Scholar
- . Queyranne. A combinatorial algorithm for minimizing symmetric submodular functions, ACM-SIAM Symposium on Discrete Algorithms (1995), 98--101. Google ScholarDigital Library
- . Reichel and M. Skutella, Evolutionary algorithms and matroid optimization problems, in Proceedings of the 9th Genetic and Evolutionary Computation Conference (GECCO'07), 947--954, 2007. Google ScholarDigital Library
- . Robertazzi and S. Schwartz, An accelated sequential algorithm for producing D-optimal designs. SIAM Journal on Scientific and Statistical Computing 10, 341--359. Google ScholarDigital Library
- . Schrijver. A combinatorial algorithm minimizing submodular functions in strongly polynomial time, Journal of Combinatorial Theory, Series B 80 (2000), 346--355. Google ScholarDigital Library
- . Schrijver. "Combinatorial Optimization," Volumes A-C. Springer-Verlag, Berlin, 2003.Google Scholar
- . Schulz, N. Uhan, Encouraging Cooperation in Sharing Supermodular Costs, APPROX-RANDOM 2007: 271--285 Google ScholarDigital Library
- . C. Shewry, H. P. Wynn, Maximum entropy sampling. J. Appl. Stat. 14 (1987), 165--170.Google ScholarCross Ref
- . Sviridenko. A note on maximizing a submodular set function subject to knapsack constraint. Operations Research Letters 32 (2004), 41--43. Google ScholarDigital Library
- Z. Svitkina and L. Fleischer. Submodular approximation: Sampling-based algorithms and lower bounds. In FOCS 2008. Google ScholarDigital Library
- . Vondrák.Optimal approximation for the submodular welfare problem in the value oracle model. In STOC, 2008. Google ScholarDigital Library
- . Vondrák, Personal communication, 2008.Google Scholar
Index Terms
- Non-monotone submodular maximization under matroid and knapsack constraints
Recommendations
Optimal approximation for the submodular welfare problem in the value oracle model
STOC '08: Proceedings of the fortieth annual ACM symposium on Theory of computingIn the Submodular Welfare Problem, m items are to be distributed among n players with utility functions wi: 2[m] → R+. The utility functions are assumed to be monotone and submodular. Assuming that player i receives a set of items Si, we wish to ...
Maximizing Non-monotone Submodular Functions
Submodular maximization generalizes many important problems including Max Cut in directed and undirected graphs and hypergraphs, certain constraint satisfaction problems, and maximum facility location problems. Unlike the problem of minimizing ...
Symmetry and Approximability of Submodular Maximization Problems
A number of recent results on optimization problems involving submodular functions have made use of the multilinear relaxation of the problem. These results hold typically in the value oracle model, where the objective function is accessible via a black box ...
Comments