2026-07-22T22:17:58Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:1767 2024-03-06T10:33:06Z ddc:004 open_access

On Estimation Algorithms vs Approximation Algorithms Feige, Uriel Estimation Algorithms Approximation Algorithms Combinatorial Optimization In a combinatorial optimization problem, when given an input instance, one seeks a feasible solution that optimizes the value of the objective function. Many combinatorial optimization problems are NP-hard. A way of coping with NP-hardness is by considering approximation algorithms. These algorithms run in polynomial time, and their performance is measured by their approximation ratio: the worst case ratio between the value of the solution produced and the value of the (unknown) optimal solution. In some cases the design of approximation algorithms includes a nonconstructive component. As a result, the algorithms become estimation algorithms rather than approximation algorithms: they allow one to estimate the value of the optimal solution, without actually producing a solution whose value is close to optimal. We shall present a few such examples, and discuss some open questions. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Uriel Feige 2008 Is Part Of LIPIcs, Volume 2, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2008) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2008.1767 urn:nbn:de:0030-drops-17676 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2008.1767 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode