Sparsification and subexponential approximation
From MaRDI portal
Publication:1702300
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.
Recommendations
- Complexity of SAT Problems, Clone Theory and the Exponential Time Hypothesis
- On problems as hard as CNF-SAT
- Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph
- Sub-exponential approximation schemes for CSPs: from dense to almost sparse
- New tools and connections for exponential-time approximation
Cites work
- scientific article; zbMATH DE number 1305522 (Why is no real title available?)
- scientific article; zbMATH DE number 1330033 (Why is no real title available?)
- scientific article; zbMATH DE number 2234775 (Why is no real title available?)
- An exponential time 2-approximation algorithm for bandwidth
- Approximating the minimum maximal independence number
- Approximation algorithms for combinatorial problems
- Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms
- Efficient Approximation of Combinatorial Problems by Moderately Exponential Algorithms
- Exact and approximate bandwidth
- Fixed-Parameter Approximation: Conceptual Framework and Approximability Results
- Linear degree extractors and the inapproximability of max clique and chromatic number
- Lower bounds based on the exponential time hypothesis
- On Approximate Solutions for Combinatorial Optimization Problems
- On Parameterized Approximability
- On approximating the minimum independent dominating set
- On approximation algorithms for the minimum satisfiability problem
- Optimization, approximation, and complexity classes
- Parameterized Approximation Problems
- Proof verification and the hardness of approximation problems
- Reducibility among combinatorial problems
- Sparsification and subexponential approximation
- The PCP theorem by gap amplification
- Towards strong nonapproximability results in the Lovász-Schrijver hierarchy
- Two-query PCP with subconstant error
- Which problems have strongly exponential complexity?
Cited in
(13)- Sub-exponential approximation schemes for CSPs: from dense to almost sparse
- Introducing \textsf{lop}-kernels: a framework for kernelization lower bounds
- A primal-dual approximation algorithm for \textsc{minsat}
- Sparse Compression of Expected Solution Operators
- New tools and connections for exponential-time approximation
- The exponential time hypothesis and the parameterized clique problem
- Approximation Bounds for Sparse Programs
- The Usefulness of Sparsifiable Inputs: How to Avoid Subexponential iO
- Maximum satisfiability and subexponential time
- Maximum minimal vertex cover parameterized by vertex cover
- Better approximations for tree sparsity in nearly-linear time
- Sparsification and subexponential approximation
- Maximum minimal vertex cover parameterized by vertex cover
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)
