文章基本信息

标题：The Submodular Santa Claus Problem in the Restricted Assignment Case
本地全文：下载
作者：Bamas, Etienne ; Garg, Paritosh ; Rohwedder, Lars 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2021
卷号：198
DOI：10.4230/LIPIcs.ICALP.2021.22
语种：English
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Scheduling;submodularity;approximation algorithm;hypergraph matching