Sparsification and subexponential approximation

DOI10.1007/S00236-016-0281-2zbMATH Open1408.68068arXiv1402.2843OpenAlexW2963359459MaRDI QIDQ1702300FDOQ1702300

Authors: Édouard Bonnet, Vangelis Th. Paschos 

Publication date: 28 February 2018

Published in: Acta Informatica (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

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

zbMATH Keywords

exponential time hypothesisinapproximabilitysparsificationvertex coverapproximation preserving sparsifiermin dominating setmin feedback vertex setmin set cover

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Cites Work

• Reducibility among combinatorial problems
• Approximation algorithms for combinatorial problems
• Optimization, approximation, and complexity classes
• Which problems have strongly exponential complexity?
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Proof verification and the hardness of approximation problems
• Parameterized Approximation Problems
• Lower bounds based on the exponential time hypothesis
• Title not available (Why is that?)
• Approximating the minimum maximal independence number
• On approximating the minimum independent dominating set
• Title not available (Why is that?)
• On approximation algorithms for the minimum satisfiability problem
• Exact and approximate bandwidth
• Efficient Approximation of Combinatorial Problems by Moderately Exponential Algorithms
• On Parameterized Approximability
• An exponential time 2-approximation algorithm for bandwidth
• Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms
• Fixed-Parameter Approximation: Conceptual Framework and Approximability Results
• On Approximate Solutions for Combinatorial Optimization Problems
• Title not available (Why is that?)
• Towards strong nonapproximability results in the Lovász-Schrijver hierarchy
• The PCP theorem by gap amplification
• Two-query PCP with subconstant error
• Sparsification and subexponential approximation

Cited In (13)

• A primal-dual approximation algorithm for \textsc{minsat}
• Maximum satisfiability and subexponential time
• The Usefulness of Sparsifiable Inputs: How to Avoid Subexponential iO
• Better approximations for tree sparsity in nearly-linear time
• Approximation Bounds for Sparse Programs
• Maximum minimal vertex cover parameterized by vertex cover
• Sub-exponential approximation schemes for CSPs: from dense to almost sparse
• The exponential time hypothesis and the parameterized clique problem
• New tools and connections for exponential-time approximation
• Sparse Compression of Expected Solution Operators
• Introducing \textsf{lop}-kernels: a framework for kernelization lower bounds
• 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)