# On the Configuration-LP of the Restricted Assignment Problem

arXiv: https://arxiv.org/abs/1611.01934 · HTML: https://mlsanity.com/paper/1611.01934/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Nov 2016.

## Built on by (most cited first, 1 of 1)

- [Learning-Augmented Algorithms with Explicit Predictors](https://mlsanity.com/paper/2403.07413/) (2024)

## Abstract (arXiv)

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 pij 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 pij∈pj,∞. 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 ≈ 1.9412. In this paper we significantly simplify his proof and achieve a bound of 2 - 1/6 ≈ 1.8333. As a direct consequence this provides a polynomial (2 - 1/6 + ε)-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 P = NP.