Back
Texte intégral
Doctoral thesis

Approximability of some classical graph and scheduling problems

    12.06.2009

155 p

Thèse de doctorat: Università della Svizzera italiana, 2009

Approximation algorithms
Hardness of approximation
Precedence- constrained scheduling
Job shops
Flow shops
Optimal linear arrangement
Sparsest cut
English 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 with an efficient algorithm? 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 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 2-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 a recent so-called Quasi-random PCP construction 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.
Language
  • English
Classification
Computer science and technology
License
License undefined
Identifiers
Persistent URL
https://n2t.net/ark:/12658/srd1317978
Statistics
Document views: 286 File downloads:
  • Texte intégral: 699