Cycle Cancellation for Submodular Fractional Allocations and Applications
Preprint
Abstract
We consider discrete allocation problem where $m$ indivisible goods are to be divided among $n$ agents. When agents' valuations are additive, the well-known cycle cancelling lemma by Lenstra, Shmoys, and Tardos plays a key role in design and analysis of rounding algorithms. In this paper, we prove an analogous lemma for the case of submodular valuations. Our algorithm removes cycles in the support graph of a fractional allocation while guaranteeing that each agent's value, measured using the multilinear extension, does not decrease. We demonstrate applications of the cycle-canceling algorithm, along with other ideas, to obtain new algorithms and results for three well-studied allocation objectives: max-min (Santa Claus problem), Nash social welfare (NSW), and maximin-share (MMS). For the submodular NSW problem, we obtain a $\frac{1}{5}$-approximation; for the MMS problem, we obtain a $\frac{1}{2}(1-1/e)$-approximation through new simple algorithms. For various special cases where the goods are "small" valued or the number of agents is constant, we obtain tight/best-known approximation algorithms. All our results are in the value-oracle model.
Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- The Unreasonable Fairness of Maximum Nash WelfareACM Transactions on Economics and Computation, 2019
- Nash Social Welfare for Indivisible Items under Separable, Piecewise-Linear Concave Utilities2018
- Approximating the Nash Social Welfare with Indivisible ItemsSIAM Journal on Computing, 2018
- Approximation Algorithms for Computing Maximin Share AllocationsACM Transactions on Algorithms, 2017
- APX-hardness of maximizing Nash social welfare with indivisible itemsInformation Processing Letters, 2017
- On Multiplicative Weight Updates for Concave and Submodular Function Maximization2015
- The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal IncomesJournal of Political Economy, 2011
- Maximizing a Monotone Submodular Function Subject to a Matroid ConstraintSIAM Journal on Computing, 2011
- Allocating indivisible goodsACM SIGecom Exchanges, 2005
- Approximation algorithms for scheduling unrelated parallel machinesMathematical Programming, 1990