In the welfare maximization problem, there is a set $[m]$ of items, and $n$ functions $w_i: 2^{[m]} \to \mathbb{Z}_+$. The goal is to partition the items into $n$ subsets $S_1,\ldots,S_n$ such that the sum $\sum_{i=1}^n w_i(S_i)$ is maximized. In this paper, Jan Vondrák presents several constant-factor approximation algorithms for this problem, assuming that the functions $w_i$ are monotone submodular set functions. In general, the problem cannot be solved exactly unless P = NP.

I am interested in the special case in which the $w_i$ are additive set functions (a special case of submodular), and all sets $S_i$ should be independent sets of a given matroid.

Is anything known about exact solutions to this problem?

  • 1
    $\begingroup$ This should be reducible to weighted matroid intersection. See the reduction (via making copies of elements) in Section 4.2 on assignment problems in the following paper that combines Jan Vondrak's paper with an earlier paper. chekuri.cs.illinois.edu/papers/submod_max_sicomp.pdf $\endgroup$ – Chandra Chekuri Sep 9 at 18:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.