Bamas, Etienne ;
Garg, Paritosh ;
Rohwedder, Lars
The Submodular Santa Claus Problem in the Restricted Assignment Case
Abstract
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.
BibTeX  Entry
@InProceedings{bamas_et_al:LIPIcs.ICALP.2021.22,
author = {Bamas, Etienne and Garg, Paritosh and Rohwedder, Lars},
title = {{The Submodular Santa Claus Problem in the Restricted Assignment Case}},
booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
pages = {22:122:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771955},
ISSN = {18688969},
year = {2021},
volume = {198},
editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14091},
URN = {urn:nbn:de:0030drops140912},
doi = {10.4230/LIPIcs.ICALP.2021.22},
annote = {Keywords: Scheduling, submodularity, approximation algorithm, hypergraph matching}
}
02.07.2021
Keywords: 

Scheduling, submodularity, approximation algorithm, hypergraph matching 
Seminar: 

48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Issue date: 

2021 
Date of publication: 

02.07.2021 