Randomized approximation algorithms : facility location, phylogenetic networks, Nash equilibria

J. Byrka

Research output: ThesisPhd Thesis 1 (Research TU/e / Graduation TU/e)

147 Downloads (Pure)

Abstract

Despite a great effort, researchers are unable to find efficient algorithms for a number of natural computational problems. Typically, it is possible to emphasize the hardness of such problems by proving that they are at least as hard as a number of other problems. In the language of computational complexity it means proving that the problem is complete for a certain class of problems. For optimization problems, we may consider to relax the requirement of the outcome to be optimal and accept an approximate (i.e., close to optimal) solution. For many of the problems that are hard to solve optimally, it is actually possible to efficiently find close to optimal solutions. In this thesis, we study algorithms for computing such approximate solutions.
Original languageEnglish
QualificationDoctor of Philosophy
Awarding Institution
  • Centrum voor Wiskunde en Informatica
Supervisors/Advisors
  • Aardal, Karen, Promotor
  • de Berg, Mark T., Promotor
Award date13 Oct 2008
Place of PublicationEindhoven
Publisher
Print ISBNs978-90-386-1416-8
DOIs
Publication statusPublished - 2008

Fingerprint

Dive into the research topics of 'Randomized approximation algorithms : facility location, phylogenetic networks, Nash equilibria'. Together they form a unique fingerprint.

Cite this