Thèse de doctorat : Università della Svizzera italiana, 2019 ; 2019INFO013.
There are a lot of natural problems arising in real life that can be modeled as discrete optimization problems. Unfortunately many of them are believed to be hard to solve efficiently (i.e. they cannot be solved in polynomial time unless P=NP). An approximation algorithm is one of the ways to tackle these hard optimization problems. These algorithms have polynomial running time and guarantee a...
|
Thèse de doctorat : Università della Svizzera italiana, 2021 ; 2021INFO005.
Many relevant discrete optimization problems are believed to be hard to solve efficiently (i.e. they cannot be solved in polynomial time unless P=NP). An approximation algorithm is one of the ways to tackle these hard optimization problems. These algorithms have polynomial running time and compute a feasible solution whose value is within a proven factor (approximation factor) of the optimal...
|
Thèse de doctorat : Università della Svizzera italiana, 2010 ; 2010INFO003.
We study the approximability of scheduling problems in different contexts. We first give a short introduction to the field of scheduling theory and present a simple single machine scheduling problem that will form the base for all variants considered in the remainder of this thesis. We point out that this scheduling problem, though long known to be efficiently solvable in its original form,...
|
Thèse de doctorat : Università della Svizzera italiana, 2009 ; 2009INFO003.
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...
|