2026-10-02T08:23:21Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26044 2026-09-23T23:58:38Z ddc:004 open_access

Submodular Max-Min Allocation Under Identical Valuations Boehmer, Kimon Submodularity Approximation algorithms Allocation Configuration LP In the problem of Submodular Max-Min Allocation, we are given a set of items, a set of players, and monotone submodular valuation functions that represent the satisfaction of a player with a certain subset of items. The goal is to find an allocation of the items to the players that maximizes the lowest satisfaction among all players. We study this problem in the special case where all players have the same valuation function. We devise a greedy algorithm which gives a 0.4-approximation, improving the previously best factor of 10/27 ≈ 0.37 by Uziahu and Feige. Furthermore, we study the integrality gap of the configuration LP when players have identical valuations. By constructing a variable assignment to the dual from a primal integral solution, we give the first constant upper bound on the integrality gap for submodular valuations. Generalizing the result to the case where players' allocations must be independent in k given matroids, we derive a 𝒪(k)-estimation algorithm for max-min allocation subject to k matroid constraints under identical valuations. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kimon Boehmer 2026 Is Part Of LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2026.8 urn:nbn:de:0030-drops-260446 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.8 eng https://creativecommons.org/licenses/by/4.0/legalcode