2026-08-15T21:27:02Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14091 2024-03-06T10:53:26Z ddc:004 open_access

The Submodular Santa Claus Problem in the Restricted Assignment Case Bamas, Etienne Garg, Paritosh Rohwedder, Lars Scheduling submodularity approximation algorithm hypergraph matching The submodular Santa Claus problem was introduced in a seminal work by Goemans, Harvey, Iwata, and Mirrokni (SODA'09) as an application of their structural result. In the mentioned problem n unsplittable resources have to be assigned to m players, each with a monotone submodular utility function f_i. The goal is to maximize min_i f_i(S_i) where S₁,...,S_m is a partition of the resources. The result by Goemans et al. implies a polynomial time O(n^{1/2 +ε})-approximation algorithm. Since then progress on this problem was limited to the linear case, that is, all f_i are linear functions. In particular, a line of research has shown that there is a polynomial time constant approximation algorithm for linear valuation functions in the restricted assignment case. This is the special case where each player is given a set of desired resources Γ_i and the individual valuation functions are defined as f_i(S) = f(S ∩ Γ_i) for a global linear function f. This can also be interpreted as maximizing min_i f(S_i) with additional assignment restrictions, i.e., resources can only be assigned to certain players. In this paper we make comparable progress for the submodular variant: If f is a monotone submodular function, we can in polynomial time compute an O(log log(n))-approximate solution. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Etienne Bamas and Paritosh Garg and Lars Rohwedder 2021 Is Part Of LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2021.22 urn:nbn:de:0030-drops-140912 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.22 eng https://creativecommons.org/licenses/by/4.0/legalcode