2008/05/17 by Jan Vondrák · 8 citations
Computer Science · #Complexity and Algorithms in Graphs #Cryptography and Data Security #Optimization and Search Problems
paper · doi:10.1145/1374376.1374389
openalex publication_date 2008/05/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/03
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: maxf(S): S ∈ I, where f is monotone submodular and I is the collection of independent sets in some matroid.