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.2843v2Date
2018Journal name
Acta InformaticaVolume
55Number
1Publisher
Springer
Pages
1-15
Publication identifier
Metadata
Show full item recordAuthor(s)
Bonnet, Édouard
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
sparsificationRelated items
Showing items related by title and author.
-
Escoffier, Bruno; Kim, Eun Jung; Paschos, Vangelis; Bonnet, Édouard (2013) Communication / Conférence
-
Bonnet, Édouard; Escoffier, Bruno; Kim, Eun Jung; Paschos, Vangelis (2015) Article accepté pour publication ou publié
-
Bonnet, Édouard; Paschos, Vangelis; Sikora, Florian (2016) Article accepté pour publication ou publié
-
Bonnet, Edouard; Escoffier, Bruno; Paschos, Vangelis; Stamoulis, Georgios (2018) Article accepté pour publication ou publié
-
Bonnet, Édouard; Lampis, Michael; Paschos, Vangelis (2018) Article accepté pour publication ou publié