License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.SOSA.2018.11
URN: urn:nbn:de:0030-drops-83012
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8301/
Go to the corresponding OASIcs Volume Portal

Jansen, Klaus ; Rohwedder, Lars

Compact LP Relaxations for Allocation Problems

pdf-format:
OASIcs-SOSA-2018-11.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{jansen_et_al:OASIcs:2018:8301,
  author =	{Klaus Jansen and Lars Rohwedder},
  title =	{{Compact LP Relaxations for Allocation Problems}},
  booktitle =	{1st Symposium on Simplicity in Algorithms (SOSA 2018)},
  pages =	{11:1--11:19},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-064-4},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{61},
  editor =	{Raimund Seidel},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8301},
  URN =		{urn:nbn:de:0030-drops-83012},
  doi =		{10.4230/OASIcs.SOSA.2018.11},
  annote =	{Keywords: Linear programming, unrelated machines, makespan, max-min, restricted assignment, santa claus}
}

Keywords: Linear programming, unrelated machines, makespan, max-min, restricted assignment, santa claus
Collection: 1st Symposium on Simplicity in Algorithms (SOSA 2018)
Issue Date: 2018
Date of publication: 05.01.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI