• 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

Sparsification and subexponential approximation

Thumbnail
Date
2018
Link to item file
https://arxiv.org/abs/1402.2843v2
Dewey
Méthodes informatiques spéciales
Sujet
sparsification
Journal issue
Acta Informatica
Volume
55
Number
1
Publication date
02-2018
Article pages
1-15
Publisher
Springer
DOI
http://dx.doi.org/10.1007/s00236-016-0281-2
URI
https://basepub.dauphine.fr/handle/123456789/18928
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Bonnet, Édouard
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)
Instance sparsification is well-known in the world of exact computation since it is very closely linked to the Exponential Time Hypothesis. In this paper, we extend the concept of sparsification in order to capture subexponential time approximation. We develop a new tool for inapproximability, called approximation preserving sparsification, and use it in order to get strong inapproximability results in subexponential time for several fundamental optimization problems such as min dominating set , min feedback vertex set , min set cover, min feedback arc set, and others.

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