Thumbnail

Moderately Exponential Approximation: Bridging the Gap Between Exact Computation and Polynomial Approximation

Paschos, Vangelis (2013), Moderately Exponential Approximation: Bridging the Gap Between Exact Computation and Polynomial Approximation, in Migdalas, Athanasios; Sifaleras, Angelo; Georgiadis, Christos K.; Papathanasiou, Jason; Stiakakis, Emmanuil, Optimization Theory, Decision Making, and Operations Research Applications, Springer : Berlin, p. 1-14. 10.1007/978-1-4614-5134-1_1

View/Open
Type
Communication / Conférence
Date
2013
Conference title
1st International Symposium and 10th Balkan Conference on Operational Research (BALCOR 2011)
Conference date
2011-09
Conference city
Thessalonique
Conference country
Greece
Book title
Optimization Theory, Decision Making, and Operations Research Applications
Book author
Migdalas, Athanasios; Sifaleras, Angelo; Georgiadis, Christos K.; Papathanasiou, Jason; Stiakakis, Emmanuil
Publisher
Springer
Series title
Springer Proceedings in Mathematics & Statistics
Series number
vol 31
Published in
Berlin
ISBN
978-1-4614-5133-4
Number of pages
359
Pages
1-14
Publication identifier
Metadata
Show full item record
Author(s)
Paschos, Vangelis
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)
This paper proposes a way to bring together two seemingly “foreign” domains that are the polynomial approximation and the exact computation for NP-hard problems. We show how one can match ideas from both areas in order to design approximation algorithms achieving ratios unachievable in polynomial time (unless a very unlikely complexity conjecture is confirmed) with worst-case complexity much lower (though super-polynomial) than that of an exact computation.
Subjects / Keywords
NP-hard problems; polynomial approximation