THESIS
2019
ix, 79 pages : illustrations ; 30 cm
Abstract
The max-min fair allocation problem, also known as the Santa Claus problem, is a fundamental
problem in combinatorial optimization. Given a set of players P, a set of
indivisible resources R, and a set of non-negative values {v
pr}
p∈P,r∈R, an allocation is a
partition of R into disjoint subsets {C
p}
p∈P so that each player p is assigned the resources
in C
p. We hope to find a fair allocation of resources to players so that the welfare of the
least lucky player is maximized. More precisely, we want to maximize min
pΣ
r∈Cp v
pr. In
the restricted case of this problem, we have v
pr ∈ {v
r, 0}. That is, each resource r has an
intrinsic value v
r, and it is worth value v
r to those players who desire it and value 0 to
those who do not.
This thesis investigates the restricted case of the probl...[
Read more ]
The max-min fair allocation problem, also known as the Santa Claus problem, is a fundamental
problem in combinatorial optimization. Given a set of players P, a set of
indivisible resources R, and a set of non-negative values {v
pr}
p∈P,r∈R, an allocation is a
partition of R into disjoint subsets {C
p}
p∈P so that each player p is assigned the resources
in C
p. We hope to find a fair allocation of resources to players so that the welfare of the
least lucky player is maximized. More precisely, we want to maximize min
pΣ
r∈Cp v
pr. In
the restricted case of this problem, we have v
pr ∈ {v
r, 0}. That is, each resource r has an
intrinsic value v
r, and it is worth value v
r to those players who desire it and value 0 to
those who do not.
This thesis investigates the restricted case of the problem, namely, the restricted max-min
fair allocation. With regard to this problem, the configuration LP is the only LP
relaxation known to have a constant integrality gap, and it plays an important role in
estimating and approximating the optimal solution. Our first result is an improvement of
the upper bound for the integrality gap from 4 to 3+21/26. It is obtained by giving a tighter
analysis of a local search algorithm in the literature. Hence, by solving the configuration
LP, we can estimate the optimal solution value of within a factor of 3+21/26. However, as the
local search is not known to run in polynomial time, it does not lead to a polynomial-time
approximation algorithm. Prior to our work, the best approximation ratio that can be
achieved in polynomial time is 6 + 2√3 + δ, where δ is an arbitrarily small constant. We
proposed two polynomial-time approximation algorithms. Our first algorithm achieves an
approximation ratio of 6 + δ. The algorithm and its analysis are purely combinatorial.
Our second algorithm achieves an approximation ratio of 4 + δ. This algorithm is also
purely combinatorial while its analysis make use of the configuration LP. It generalizes
the local search used in the integrality gap result.
Post a Comment