Design of approximation algorithms for scheduling on unrelated machines

• Applicant: Professor Dr. Klaus Jansen
• Subject Area: Theoretical Computer Science
• Term: from 2011 to 2018
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 197234132

In this project we work on several open questions regarding the problem Scheduling on Unrelated Machines with makespan minimization. This is a classical combinatorial problem, in which a set of jobs has to be distributed among a set of machines. Each job j has a processing time p_ij depending on the machine i it is assigned to. The objective is to minimize the maximum load among all machines, the makespan.Our research has a particular focus on (but is not limited to) the study of the Restricted Assignment problem, in which p_ij is either p_j (independent of the machine) or infinite. For this special case a local search algorithm was discovered, which produces a solution of value at most 33/17 OPT_LP, where OPT_LP is the optimum value of the configuration LP, a strong LP relaxation. So far, this algorithm has only been used to argue about the integrality gap of the configuration LP, since no good bounds on its running time are known. A polynomial variant would have a great impact, because this would improve on the 2-approximation established more than 25 years ago.Additionally we want to study LP/SDP hierarchies, such as the Lasserre hierarchy, in the context of problem Scheduling on Unrelated Machines. The interesting question here iswhether these hierarchies can be used to find an even stronger relaxation than the configuration LP.

• DFG Programme: Research Grants