
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érenceDate
2013Conference title
1st International Symposium and 10th Balkan Conference on Operational Research (BALCOR 2011)Conference date
2011-09Conference city
ThessaloniqueConference country
GreeceBook title
Optimization Theory, Decision Making, and Operations Research ApplicationsBook author
Migdalas, Athanasios; Sifaleras, Angelo; Georgiadis, Christos K.; Papathanasiou, Jason; Stiakakis, EmmanuilPublisher
Springer
Series title
Springer Proceedings in Mathematics & StatisticsSeries number
vol 31Published in
Berlin
ISBN
978-1-4614-5133-4
Number of pages
359Pages
1-14
Publication identifier
Metadata
Show full item recordAuthor(s)
Paschos, VangelisLaboratoire 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 approximationRelated items
Showing items related by title and author.
-
Demange, Marc; Monnot, Jérôme; Paschos, Vangelis (1999) Article accepté pour publication ou publié
-
Paschos, Vangelis (2015) Article accepté pour publication ou publié
-
Demange, Marc; Paschos, Vangelis (1996) Article accepté pour publication ou publié
-
Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis (2011) Article accepté pour publication ou publié
-
Paschos, Vangelis; Escoffier, Bruno; Bourgeois, Nicolas (2009) Article accepté pour publication ou publié