Sparsification and subexponential approximation
From MaRDI portal
Publication:1702300
DOI10.1007/S00236-016-0281-2zbMATH Open1408.68068arXiv1402.2843OpenAlexW2963359459MaRDI QIDQ1702300
Author name not available (Why is that?)
Publication date: 28 February 2018
Published in: (Search for Journal in Brave)
Abstract: 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 as Max Independent Set, Min Dominating Set, Min Feedback Vertex Set, and Min Set Cover.
Full work available at URL: https://arxiv.org/abs/1402.2843
No records found.
No records found.
This page was built for publication: Sparsification and subexponential approximation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1702300)
