ABSTRACT
In 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 maximize the total utility ∑i=1n wi(Si). In this paper, we work in the value oracle model where the only access to the utility functions is through a black box returning wi(S) for a given set S. Submodular Welfare is in fact a special case of the more general problem of submodular maximization subject to a matroid constraint: max{f(S): S ∈ I}, where f is monotone submodular and I is the collection of independent sets in some matroid.
For both problems, a greedy algorithm is known to yield a 1/2-approximation [21, 16]. In special cases where the matroid is uniform (I = S: |S| ≤ k) [20] or the submodular function is of a special type [4, 2], a (1-1/e)-approximation has been achieved and this is optimal for these problems in the value oracle model [22, 6, 15]. A (1-1/e)-approximation for the general Submodular Welfare Problem has been known only in a stronger demand oracle model [4], where in fact 1-1/e can be improved [9].
In this paper, we develop a randomized continuous greedy algorithm which achieves a (1-1/e)-approximation for the Submodular Welfare Problem in the value oracle model. We also show that the special case of n equal players is approximation resistant, in the sense that the optimal (1-1/e)-approximation is achieved by a uniformly random solution. Using the pipage rounding technique [1, 2], we obtain a (1-1/e)-approximation for submodular maximization subject to any matroid constraint. The continuous greedy algorithm has a potential of wider applicability, which we demonstrate on the examples of the Generalized Assignment Problem and the AdWords Assignment Problem.
- A. Ageev and M. Sviridenko. Pipage rounding: a new method of constructing algorithms with proven performance guarantee, J. of Combinatorial Optimization 8 (2004), 307--328.Google ScholarCross Ref
- G. Calinescu, C. Chekuri, M. Pal and J. Vondrak. Maximizing a submodular set function subject to a matroid constraint, Proc. of 12th IPCO (2007), 182--196. Google ScholarDigital Library
- C. Chekuri and A. Kumar. Maximum coverage problem with group budget constraints and applications, Proc. of APPROX} 2004, Lecture Notes in Computer Science 3122, 72--83.Google ScholarCross Ref
- S. Dobzinski and M. Schapira. An improved approximation algorithm for combinatorial auctions with submodular bidders, Proc. of 17th SODA (2006), 1064--1073. Google ScholarDigital Library
- J. Edmonds. Matroids, submodular functions and certain polyhedra, Combinatorial Structures and Their Applications} (1970), 69--87.Google Scholar
- U. Feige. A threshold of ln n for approximating Set Cover, Journal of the ACM 45 (1998), 634--652. Google ScholarDigital Library
- U. Feige. Maximizing social welfare when utility functions are subadditive, Proc. of 38th STOC (2006), 41--50. Google ScholarDigital Library
- U. Feige, V. Mirrokni and J. Vondrak. Maximizing non-monotone submodular functions, Proc. of 48th FOCS (2007), 461--471. Google ScholarDigital Library
- U. Feige and J. Vondrak. Approximation algorithms for combinatorial allocation problems: Improving the factor of 1-1/e, Proc. of 47th FOCS (2006), 667--676. Google ScholarDigital Library
- L. Fleischer, S. Fujishige and S. Iwata. A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions, Journal of the ACM 48:4 (2001), 761--777. Google ScholarDigital Library
- L. Fleischer, M. X. Goemans, V. Mirrokni and M. Sviridenko. Tight approximation algorithms for maximum general assignment problems, Proc. of 17th ACM-SIAM SODA (2006), 611--620. Google ScholarDigital Library
- P. Goundan and A. Schulz. Revisiting the greedy approach to submodular set function maximization, manuscript (2007).Google Scholar
- J. Hastad. Clique is hard to approximate within n1-ε, Acta Mathematica 182 (1999), 105--142.Google ScholarCross Ref
- K. Jansen and G. Zhang. On rectangle packing: maximizing benefits, Proc. of 15th ACM-SIAM SODA (2004), 204--213. Google ScholarDigital Library
- S. Khot, R. Lipton, E. Markakis and A. Mehta. Inapproximability results for combinatorial auctions with submodular utility functions, Proc. of WINE 2005, Lecture Notes in Computer Science 3828, 92--101. Google ScholarDigital Library
- B. Lehmann, D. J. Lehmann and N. Nisan. Combinatorial auctions with decreasing marginal utilities, ACM Conference on El. Commerce 2001, 18--28. Google ScholarDigital Library
- B. Lehmann, D. J. Lehmann and N. Nisan. Combinatorial auctions with decreasing marginal utilities (journal version), Games and Economic Behavior 55 (2006), 270--296.Google ScholarCross Ref
- L. Lovasz. Submodular functions and convexity. A. Bachem et al., editors, Mathematical Programmming: The State of the Art, 235--257.Google Scholar
- V. Mirrokni, M. Schapira and J. Vondrak. Tight information-theoretic lower bounds for welfare maximization in combinatorial auctions, manuscript (2007). Google ScholarDigital Library
- G. 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
- M. L. Fisher, G. L. Nemhauser and L. A. Wolsey. An analysis of approximations for maximizing submodular set functions II, Math. Programming Study 8 (1978), 73--87.Google ScholarCross Ref
- G. L. Nemhauser and L. A. Wolsey. Best algorithms for approximating the maximum of a submodular set function, Math. Operations Research 3:3 (1978), 177--188.Google ScholarDigital Library
- A. Schrijver. A combinatorial algorithm minimizing submodular functions in strongly polynomial time, Journal of Combinatorial Theory, Series B 80 (2000), 346--355. Google ScholarDigital Library
- A. Schrijver. Combinatorial optimization - polyhedra and efficiency, Springer-Verlag Berlin Heidelberg, 2003.Google Scholar
- M. Sviridenko. A note on maximizing a submodular set function subject to knapsack constraint, Operations Research Letters 32 (2004), 41--43. Google ScholarDigital Library
- L. Wolsey. Maximizing real-valued submodular functions: Primal and dual heuristics for location problems, Math. of Operations Research 7 (1982), 410--425.Google ScholarDigital Library
- D. Zuckerman. Linear degree extractors and inapproximability, Theory of Computing 3 (2007), 103--128.Google ScholarCross Ref
Index Terms
- Optimal approximation for the submodular welfare problem in the value oracle model
Recommendations
Non-monotone submodular maximization under matroid and knapsack constraints
STOC '09: Proceedings of the forty-first annual ACM symposium on Theory of computingSubmodular 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 ...
Welfare maximization and the supermodular degree
ITCS '13: Proceedings of the 4th conference on Innovations in Theoretical Computer ScienceGiven a set of items and a collection of players, each with a nonnegative monotone valuation set function over the items, the welfare maximization problem requires that every item be allocated to exactly one player, and one wishes to maximize the sum of ...
Limitations of Randomized Mechanisms for Combinatorial Auctions
FOCS '11: Proceedings of the 2011 IEEE 52nd Annual Symposium on Foundations of Computer ScienceThe design of computationally efficient and incentive compatible mechanisms that solve or approximate fundamental resource allocation problems is the main goal of algorithmic mechanism design. A central example in both theory and practice is welfare-...
Comments