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