License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2021.22
URN: urn:nbn:de:0030-drops-140912
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14091/
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:1--22:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-195-5},
ISSN = {1868-8969},
year = {2021},
volume = {198},
editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14091},
URN = {urn:nbn:de:0030-drops-140912},
doi = {10.4230/LIPIcs.ICALP.2021.22},
annote = {Keywords: Scheduling, submodularity, approximation algorithm, hypergraph matching}
}
|
Keywords: |
|
Scheduling, submodularity, approximation algorithm, hypergraph matching |
|
Collection: |
|
48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
02.07.2021 |
