• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

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

Thumbnail
View/Open
presentation_1.pdf (690.0Kb)
Date
2013
Collection title
Springer Proceedings in Mathematics & Statistics
Collection Id
vol 31
Dewey
Recherche opérationnelle
Sujet
NP-hard problems; polynomial approximation
DOI
http://dx.doi.org/10.1007/978-1-4614-5134-1_1
Conference name
1st International Symposium and 10th Balkan Conference on Operational Research (BALCOR 2011)
Conference date
09-2011
Conference city
Thessalonique
Conference country
Greece
Book title
Optimization Theory, Decision Making, and Operations Research Applications
Author
Migdalas, Athanasios; Sifaleras, Angelo; Georgiadis, Christos K.; Papathanasiou, Jason; Stiakakis, Emmanuil
Publisher
Springer
Publisher city
Berlin
Year
2013
Pages number
359
ISBN
978-1-4614-5133-4
Book URL
http://dx.doi.org/10.1007/978-1-4614-5134-1
URI
https://basepub.dauphine.fr/handle/123456789/10799
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Paschos, Vangelis
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Type
Communication / Conférence
Item number of pages
1-14
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.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.