Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: On the Configuration-LP of the Restricted Assignment Problem   We consider the classical problem of Scheduling on Unrelated Machines. In
this problem a set of jobs is to be distributed among a set of machines and the
maximum load (makespan) is to be minimized. The processing time $p_{ij}$ of a
job $j$ depends on the machine $i$ it is assigned to. Lenstra, Shmoys and
Tardos gave a polynomial time $2$-approximation for this problem. In this paper
we focus on a prominent special case, the Restricted Assignment problem, in
which $p_{ij}\in\{p_j,\infty\}$. The configuration-LP is a linear programming
relaxation for the Restricted Assignment problem. It was shown by Svensson that
the multiplicative gap between integral and fractional solution, the
integrality gap, is at most $2 - 1/17 \approx 1.9412$. In this paper we
significantly simplify his proof and achieve a bound of $2 - 1/6 \approx
1.8333$. As a direct consequence this provides a polynomial $(2 - 1/6 +
\epsilon)$-estimation algorithm for the Restricted Assignment problem by
approximating the configuration-LP. The best lower bound known for the
integrality gap is $1.5$ and no estimation algorithm with a guarantee better
than $1.5$ exists unless $\mathrm{P} = \mathrm{NP}$.

20
The categories of this paper are: acc-phys
9
The categories of this paper are: nlin
3
The categories of this paper are: physics
19
The categories of this paper are: eess
32
The categories of this paper are: atom-ph
0
The categories of this paper are: hep-ph
31
The categories of this paper are: ao-sci
7
The categories of this paper are: hep-th
4
The categories of this paper are: cond-mat
23
The categories of this paper are: solv-int
18
The categories of this paper are: econ
28
The categories of this paper are: alg-geom
36
The categories of this paper are: cmp-lg
26
The categories of this paper are: bayes-an
22
The categories of this paper are: chao-dyn
21
The categories of this paper are: adap-org