Sudmodular welfare maximization is the problem of allocating items among agents with different valuations, represented by submodular set functions, such that the sum of agents' values is as large as possible. There is a 0.5-factor deterministic approximation algorithm, and a ~0.63-factor randomized approximation algorithm.
I am looking for a polynomial-time algorithm with an additive approximation guarantee, such as the following: "The welfare of the allocation found by the algorithm is at least as high as the optimal welfare minus the largest marginal value of a single item".
Does anything similar to this exist?
