Compact LP Relaxations for Allocation Problems

Jansen, Klaus; Rohwedder, Lars

doi:10.4230/OASIcs.SOSA.2018.11

File

OASIcs.SOSA.2018.11.pdf

Filesize: 0.51 MB
19 pages

Document Identifiers

DOI: 10.4230/OASIcs.SOSA.2018.11
URN: urn:nbn:de:0030-drops-83012

Author Details

Klaus Jansen

Lars Rohwedder

Cite AsGet BibTex

Klaus Jansen and Lars Rohwedder. Compact LP Relaxations for Allocation Problems. In 1st Symposium on Simplicity in Algorithms (SOSA 2018). Open Access Series in Informatics (OASIcs), Volume 61, pp. 11:1-11:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/OASIcs.SOSA.2018.11

Abstract

We consider the restricted versions of Scheduling on Unrelated Machines and the Santa Claus problem. In these problems we are given a set of jobs and a set of machines. Every job j has a size p_j and a set of allowed machines \Gamma(j), i.e., it can only be assigned to those machines. In the first problem, the objective is to minimize the maximum load among all machines; in the latter problem it is to maximize the minimum load. For these problems, the strongest LP relaxation known is the configuration LP. The configuration LP has an exponential number of variables and it cannot be solved exactly unless P = NP. Our main result is a new LP relaxation for these problems. This LP has only O(n^3) variables and constraints. It is a further relaxation of the configuration LP, but it obeys the best bounds known for its integrality gap (11/6 and 4). For the configuration LP these bounds were obtained using two local search algorithm. These algorithms, however, differ significantly in presentation. In this paper, we give a meta algorithm based on the local search ideas. With an instantiation for each objective function, we prove the bounds for the new compact LP relaxation (in particular, for the configuration LP). This way, we bring out many analogies between the two proofs, which were not apparent before.

Keywords

Linear programming
unrelated machines
makespan
max-min
restricted assignment
santa claus

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

References

Chidambaram Annamalai. Lazy local search meets machine scheduling. CoRR, abs/1611.07371, 2016. URL: http://arxiv.org/abs/1611.07371.
Chidambaram Annamalai, Christos Kalaitzis, and Ola Svensson. Combinatorial algorithm for restricted max-min fair allocation. In Piotr Indyk, editor, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 1357-1372. SIAM, 2015. URL: http://dx.doi.org/10.1137/1.9781611973730.90.
Arash Asadpour, Uriel Feige, and Amin Saberi. Santa claus meets hypergraph matchings. ACM Trans. Algorithms, 8(3):24:1-24:9, 2012. URL: http://dx.doi.org/10.1145/2229163.2229168.
Nikhil Bansal and Maxim Sviridenko. The santa claus problem. In Jon M. Kleinberg, editor, Proceedings of the 38th Annual ACM Symposium on Theory of Computing, Seattle, WA, USA, May 21-23, 2006, pages 31-40. ACM, 2006. URL: http://dx.doi.org/10.1145/1132516.1132522.
Ivona Bezáková and Varsha Dani. Allocating indivisible goods. SIGecom Exchanges, 5(3):11-18, 2005. URL: http://dx.doi.org/10.1145/1120680.1120683.
Tomás Ebenlendr, Marek Krcál, and Jirí Sgall. Graph balancing: A special case of scheduling unrelated parallel machines. Algorithmica, 68(1):62-80, 2014. URL: http://dx.doi.org/10.1007/s00453-012-9668-9.
Klaus Jansen and Lars Rohwedder. On the configuration-lp of the restricted assignment problem. In Philip N. Klein, editor, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 2670-2678. SIAM, 2017. URL: http://dx.doi.org/10.1137/1.9781611974782.176.
Klaus Jansen and Lars Rohwedder. A quasi-polynomial approximation for the restricted assignment problem. In Friedrich Eisenbrand and Jochen Könemann, editors, Integer Programming and Combinatorial Optimization - 19th International Conference, IPCO 2017, Waterloo, ON, Canada, June 26-28, 2017, Proceedings, volume 10328 of Lecture Notes in Computer Science, pages 305-316. Springer, 2017. URL: http://dx.doi.org/10.1007/978-3-319-59250-3_25.
Jan Karel Lenstra, David B. Shmoys, and Éva Tardos. Approximation algorithms for scheduling unrelated parallel machines. Math. Program., 46:259-271, 1990. URL: http://dx.doi.org/10.1007/BF01585745.
Lukás Polácek and Ola Svensson. Quasi-polynomial local search for restricted max-min fair allocation. ACM Trans. Algorithms, 12(2):13:1-13:13, 2016. URL: http://dx.doi.org/10.1145/2818695.
Ola Svensson. Santa claus schedules jobs on unrelated machines. SIAM J. Comput., 41(5):1318-1341, 2012. URL: http://dx.doi.org/10.1137/110851201.
José Verschae and Andreas Wiese. On the configuration-lp for scheduling on unrelated machines. J. Scheduling, 17(4):371-383, 2014. URL: http://dx.doi.org/10.1007/s10951-013-0359-4.