Sparsification and subexponential approximation
From MaRDI portal
Publication:1702300
DOI10.1007/s00236-016-0281-2zbMath1408.68068arXiv1402.2843MaRDI QIDQ1702300
Vangelis Th. Paschos, Édouard Bonnet
Publication date: 28 February 2018
Published in: Acta Informatica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1402.2843
vertex cover; inapproximability; sparsification; exponential time hypothesis; approximation preserving sparsifier; min dominating set; min feedback vertex set; min set cover
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68W25: Approximation algorithms