• 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

Time-approximation trade-offs for inapproximable problems

Thumbnail
Date
2018
Link to item file
https://arxiv.org/abs/1502.05828v1
Dewey
Programmation, logiciels, organisation des données
Sujet
Approximation algorithms; Exponential algorithms; Sub-exponential algorithms; Hardness of approximation
Journal issue
Journal of Computer and System Sciences
Volume
92
Publication date
03-2018
Article pages
171-180
Publisher
Elsevier
DOI
http://dx.doi.org/10.1016/j.jcss.2017.09.009
URI
https://basepub.dauphine.fr/handle/123456789/19104
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Bonnet, Édouard
Lampis, Michael
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Paschos, Vangelis
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Type
Article accepté pour publication ou publié
Abstract (EN)
In this paper we focus on problems inapproximable in polynomial time and explore how quickly their approximability improves as the allowed running time is gradually increased from polynomial to (sub-)exponential. We tackle a number of problems: For Min Independent Dominating Set, Max Induced Path, Forest and Tree, for any , a simple, known scheme gives an approximation ratio of r in time roughly . We show that, if this running time could be significantly improved, the ETH would fail. For Max Minimal Vertex Cover we give a -approximation in time . We match this with a similarly tight result. We also give a -approximation for Min ATSP in time and an r-approximation for Max Grundy Coloring in time . Finally, we investigate the approximability of Min Set Cover, when measuring the running time as a function of the number of sets in the input.

  • 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.