Feige, Uriel
On Estimation Algorithms vs Approximation Algorithms
Abstract
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 NPhard. A way of coping with NPhardness 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.
BibTeX  Entry
@InProceedings{feige:LIPIcs:2008:1767,
author = {Uriel Feige},
title = {{On Estimation Algorithms vs Approximation Algorithms}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
pages = {357363},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897088},
ISSN = {18688969},
year = {2008},
volume = {2},
editor = {Ramesh Hariharan and Madhavan Mukund and V Vinay},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2008/1767},
URN = {urn:nbn:de:0030drops17676},
doi = {http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2008.1767},
annote = {Keywords: Estimation Algorithms, Approximation Algorithms, Combinatorial Optimization}
}
2008
Keywords: 

Estimation Algorithms, Approximation Algorithms, Combinatorial Optimization 
Seminar: 

IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science

Related Scholarly Article: 


Issue date: 

2008 
Date of publication: 

2008 