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