Approximation thresholds for combinatorial optimization problems

Simple item page
dc.creatorFeige, Uriel
dc.date2003-04-28
dc.date.accessioned2026-07-07T12:12:31Z
dc.date.available2026-07-07T12:12:31Z
dc.descriptionAn NP-hard combinatorial optimization problem $Π$ is said to have an {\em approximation threshold} if there is some $t$ such that the optimal value of $Π$ can be approximated in polynomial time within a ratio of $t$, and it is NP-hard to approximate it within a ratio better than $t$. We survey some of the known approximation threshold results, and discuss the pattern that emerges from the known results.
dc.identifierhttps://arxiv.org/abs/cs/0304039
dc.identifierhttp://arxiv.org/abs/cs/0304039
dc.identifierProceedings of the ICM, Beijing 2002, vol. 3, 649--658
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/210568
dc.subjectComputational Complexity
dc.subject68Q17, 68W25
dc.subjectF.1
dc.titleApproximation thresholds for combinatorial optimization problems
dc.typetext

Files

Collections

arXiv