Abstract
We study the maxmin fair allocation problem in which a set of m indivisible items are to be distributed among n agents such that the minimum utility among all agents is maximized. In the restricted setting, the utility of each item j on agent i is either 0 or some nonnegative weight w_j. For this setting, Asadpour et al. [TALG, 2012] showed that a certain configurationLP can be used to estimate the optimal value within a factor of 4 + delta, for any delta > 0, which was recently extended by Annamalai et al. [SODA 2015] to give a polynomialtime 13approximation algorithm for the problem. For hardness results, Bezáková and Dani [SIGecom Exch., 2005] showed that it is NPhard to approximate the problem within any ratio smaller than 2.
In this paper we consider the (1, epsilon)restricted maxmin fair allocation problem, in which for some parameter epsilon in (0, 1), each item j is either heavy (w_j = 1) or light (w_j = epsilon). We show that the (1, epsilon)restricted case is also NPhard to approximate within any ratio smaller than 2. Hence, this simple special case is still algorithmically interesting.
Using the configurationLP, we are able to estimate the optimal value of the problem within a factor of 3 + delta, for any delta > 0. Extending this idea, we also obtain a quasipolynomial time (3 + 4 epsilon)approximation algorithm and a polynomial time 9approximation algorithm. Moreover, we show that as epsilon tends to 0, the approximation ratio of our polynomialtime algorithm approaches 3 + 2 sqrt{2} approx 5.83.
BibTeX  Entry
@InProceedings{chan_et_al:LIPIcs:2016:6793,
author = {TH. Hubert Chan and Zhihao Gavin Tang and Xiaowei Wu},
title = {{On (1, epsilon)Restricted MaxMin Fair Allocation Problem}},
booktitle = {27th International Symposium on Algorithms and Computation (ISAAC 2016)},
pages = {23:123:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770262},
ISSN = {18688969},
year = {2016},
volume = {64},
editor = {SeokHee Hong},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6793},
URN = {urn:nbn:de:0030drops67939},
doi = {10.4230/LIPIcs.ISAAC.2016.23},
annote = {Keywords: MaxMin Fair Allocation, Hypergraph Matching}
}
Keywords: 

MaxMin Fair Allocation, Hypergraph Matching 
Collection: 

27th International Symposium on Algorithms and Computation (ISAAC 2016) 
Issue Date: 

2016 
Date of publication: 

07.12.2016 