2026-07-22T13:28:14Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9041 2024-03-06T10:43:13Z ddc:004 open_access

Restricted Max-Min Fair Allocation Cheng, Siu-Wing Mao, Yuchen Fair allocation approximation local search The restricted max-min fair allocation problem seeks an allocation of resources to players that maximizes the minimum total value obtained by any player. It is NP-hard to approximate the problem to a ratio less than 2. Comparing the current best algorithm for estimating the optimal value with the current best for constructing an allocation, there is quite a gap between the ratios that can be achieved in polynomial time: 4+delta for estimation and 6 + 2 sqrt{10} + delta ~~ 12.325 + delta for construction, where delta is an arbitrarily small constant greater than 0. We propose an algorithm that constructs an allocation with value within a factor 6 + delta from the optimum for any constant delta > 0. The running time is polynomial in the input size for any constant delta chosen. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Siu-Wing Cheng and Yuchen Mao 2018 Is Part Of LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2018.37 urn:nbn:de:0030-drops-90418 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.37 eng https://creativecommons.org/licenses/by/3.0/legalcode