• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - No thumbnail

Sparsification and subexponential approximation

Bonnet, Édouard; Paschos, Vangelis (2018), Sparsification and subexponential approximation, Acta Informatica, 55, 1, p. 1-15. 10.1007/s00236-016-0281-2

Type
Article accepté pour publication ou publié
External document link
https://arxiv.org/abs/1402.2843v2
Date
2018
Journal name
Acta Informatica
Volume
55
Number
1
Publisher
Springer
Pages
1-15
Publication identifier
10.1007/s00236-016-0281-2
Metadata
Show full item record
Author(s)
Bonnet, Édouard cc
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Paschos, Vangelis
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
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.
Subjects / Keywords
sparsification

Related items

Showing items related by title and author.

  • Thumbnail
    On Subexponential and FPT-time Inapproximability 
    Escoffier, Bruno; Kim, Eun Jung; Paschos, Vangelis; Bonnet, Édouard (2013) Communication / Conférence
  • Thumbnail
    On Subexponential and FPT-Time Inapproximability 
    Bonnet, Édouard; Escoffier, Bruno; Kim, Eun Jung; Paschos, Vangelis (2015) Article accepté pour publication ou publié
  • Thumbnail
    Parameterized exact and approximation algorithms for maximum k-set cover and related satisfiability problems 
    Bonnet, Édouard; Paschos, Vangelis; Sikora, Florian (2016) Article accepté pour publication ou publié
  • Thumbnail
    Purely combinatorial approximation algorithms for maximum k -vertex cover in bipartite graphs 
    Bonnet, Edouard; Escoffier, Bruno; Paschos, Vangelis; Stamoulis, Georgios (2018) Article accepté pour publication ou publié
  • Thumbnail
    Time-approximation trade-offs for inapproximable problems 
    Bonnet, Édouard; Lampis, Michael; Paschos, Vangelis (2018) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo