|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'504'928
Articles rated: 2609
25 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
On ($1$, $epsilon$)-Restricted Max-Min Fair Allocation Problem | | T-H. Hubert Chan
; Zhihao Gavin Tang
; Xiaowei Wu
; | | Date: |
24 Nov 2016 | | Abstract: | We study the max-min 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 non-negative weight $w_j$.
For this setting, Asadpour et al. showed that a certain configuration-LP 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. to give a
polynomial-time $13$-approximation algorithm for the problem. For hardness
results, Bezakova and Dani showed that it is NP-hard to approximate the
problem within any ratio smaller than $2$.
In this paper we consider the $(1,epsilon)$-restricted max-min fair
allocation problem in which each item $j$ is either heavy $(w_j = 1)$ or light
$(w_j = epsilon)$, for some parameter $epsilon in (0,1)$. We show that the
$(1,epsilon)$-restricted case is also NP-hard to approximate within any ratio
smaller than $2$. Hence, this simple special case is still algorithmically
interesting.
Using the configuration-LP, 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 quasi-polynomial time $(3+4epsilon)$-approximation algorithm
and a polynomial time $9$-approximation algorithm. Moreover, we show that as
$epsilon$ tends to $0$, the approximation ratio of our polynomial-time
algorithm approaches $3+2sqrt{2}approx 5.83$. | | Source: | arXiv, 1611.8060 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER