Seminars at the Faculty of Informatics

Approximability of Some Classical Graph and Scheduling Problems

Mr. Ola SVENSSON, Friday, June 12th, 2009 at 09:30, room SI-008

 

The dissertation committee is composed of:

  • Prof. Dr. Luca Maria Gambardella, IDSIA/Universitą della Svizzera italiana, Switzerland (advisor)
  • Prof. Dr. Klaus Jansen, Christian-Albrechts-Universität zu Kiel, Germany (external member)
  • Dr. Monaldo Mastrolilli, IDSIA, Switzerland (internal member)
  • Prof. Dr. Andreas S. Schulz, Massachusetts Institute of Technology, USA (external member)
  • Prof. Dr. Thomas Shrimpton, Universitą della Svizzera italiana, Switzerland (internal member)

 

ABSTRACT:
Approximation algorithms are motivated by the fact that for many important optimization problems we cannot hope to efficiently find an optimal solution (unless P=NP). Instead, we have to settle for second best --- a solution that is close to being optimal. A natural question that arises is: how close to the optimal solution can one get in efficient time?  The past two decades have seen major progress in answering this question for several fundamental optimization problems, including clique, set-cover, and graph coloring. In spite of this progress, our understanding of approximability for some classes of problems has remained especially weak.  In this thesis we address several prominent open problems in the area of approximation algorithms for two such classes, namely machine scheduling and certain graph problems.

The first part of the thesis is devoted to the study of the classical precedence-constrained single machine scheduling problem with the weighted sum of completion times objective.  By exploiting the scheduling problem's relationship to partial orders and vertex cover, we present a framework that achieves a better approximation guarantee as soon as the precedence constraints have low complexity (i.e. low dimension).  We also complement these positive results by giving the first inapproximability result for the scheduling problem together with evidences that the various $-approximation algorithms might be tight.

In the second part, we focus on the uniform sparsest cut and optimal linear arrangement graph problems. These classical graph problems are typical cases of problems for which neither a hardness of approximation result, nor a `good' approximation algorithm exists. We use the recent so-called Quasi-random PCP construction by Khot to give the first hardness of approximation results for these problems that rule out the existence of a polynomial time approximation scheme for each of these problems.

We conclude the thesis by considering two notorious scheduling problems in shop environments, namely the job shop problem together with the more restricted flow shop problem.  We close a major open problem in scheduling theory by providing stronger inapproximability results for these problems. More precisely, we give a gap-preserving reduction from graph coloring that gives an inapproximability result that matches the best known approximation algorithm for the general version of flow shops, where jobs are not required to be processed on each machine.  Our result is also tight for the more general acyclic job shop problem and gives the first non-constant hardness of approximation result for the job shop problem.