@techreport{Report-025-2010,
Title = {On the Configuration-LP for Scheduling on Unrelated Machines},
Author = {Jose Verschae and Andreas Wiese},
Year = {2010},
Number = {025},
Month = {november},
Type = {Preprint},
Institution = {Technische Universit\"at Berlin, Institut f\"ur Mathematik},
Abstract = {One of the most important open problems in machine scheduling is the problem of scheduling a set of jobs on unrelated machines to minimize the makespan. The best known approximation algorithm for this problem guarantees an approximation factor of 2. It is known to be NP-hard to approximate with a better ratio than 3/2. Closing this gap has been open for over 20 years. The best known approximation factors are achieved by LP-based algorithms. The strongest known linear program formulation for the problem is the configuration-LP. We show that the configuration-LP has an integrality gap of 2 even for the special case of unrelated graph balancing, where each job can be assigned to at most two machines. In particular, our result implies that a large family of cuts does not help to diminish the integrality gap of the canonical assignment-LP. Also, we present cases of the problem which can be approximated with a better factor than 2. They constitute valuable insights for constructing an NP-hardness reduction which improves the known lower bound. Very recently Svensson studied the restricted assignment case, where each job can only be assigned to a given set of machines on which it has the same processing time. He shows that in this setting the configuration-LP has an integrality gap of 33/17. Hence, our result imply that the unrelated graph balancing case is significantly more complex than the restricted assignment case. Then we turn to another objective function: maximizing the minimum machine load. For the case that every job can be assigned to at most two machines we give a purely combinatorial 2-approximation which is best possible, unless P=NP. This improves on the computationally costly LP-based (2+eps)-approximation algorithm by Chakrabarty et al.},
Url = {http://www.redaktion.tu-berlin.de/fileadmin/i26/download/AG_DiskAlg/FG_KombOptGraphAlg/preprints/2010/Report-025-2010.pdf},
Keywords = {Scheduling, Unrelated Machines, Configuration-LP, MaxMin-allocation problem, Integrality Gap}
}