Refine my results

Centrality of trees for capacitated $$k$$ k -center

An, Hyung-Chan ; Bhaskara, Aditya ; Chekuri, Chandra ; Gupta, Shalmoli ; Madan, Vivek ; Svensson, Ola

In: Mathematical Programming, 2015, vol. 154, no. 1-2, p. 29-53

Approximation algorithms for survivable network design

Jabal Ameli, Afrouz ; Grandoni, Fabrizio (Dir.)

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...

Approximation algorithms for two-dimensional geometric packing problems

Gálvez, Waldo ; Grandoni, Fabrizio (Dir.)

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...

New approaches to multi-objective optimization

Grandoni, Fabrizio ; Ravi, R. ; Singh, Mohit ; Zenklusen, Rico

In: Mathematical Programming, 2014, vol. 146, no. 1-2, p. 525-554

Approximability of precedence constrained and robust scheduling problems

Mutsanas, Nikos ; Gambardella, Luca Maria (Dir.) ; Mastrolilli, Monaldo (Codir.)

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,...

Approximability of some classical graph and scheduling problems

Svensson, Ola Nils Anders ; Mastrolilli, Monaldo (Dir.)

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...