2026-09-10T09:44:35Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27738 2026-09-09T12:19:36Z ddc:004 open_access

Cycle Cancellation for Submodular Fractional Allocations and Applications Chekuri, Chandra Kulkarni, Pooja Mehta, Ruta Vondràk, Jan Submodular Optimization Allocation Problems Fair Division We consider discrete allocation problems where m indivisible goods need to be allocated among n agents. When agents' valuation functions are additive, the well-known cycle canceling lemma [Lenstra et al., 1990; Shmoys and Tardos, 1993; Plotkin et al., 1995] plays a key role in the 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 1/5-approximation; for the MMS problem, we obtain a 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Chandra Chekuri and Pooja Kulkarni and Ruta Mehta and Jan Vondràk 2026 Is Part Of LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2026.21 urn:nbn:de:0030-drops-277384 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.21 eng https://creativecommons.org/licenses/by/4.0/legalcode