New tools and connections for exponential-time approximation
DOI10.1007/s00453-018-0512-8zbMath1430.68444arXiv1708.03515OpenAlexW2964172924WikidataQ93184208 ScholiaQ93184208MaRDI QIDQ2272598
Parinya Chalermsook, Bundit Laekhanukit, Jesper Nederlof, Nikhil Bansal, Danupon Nanongkai
Publication date: 10 September 2019
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1708.03515
Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25) Randomized algorithms (68W20)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms
- Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs
- Exact and approximate bandwidth
- Exponential-time approximation of weighted set cover
- Approximation algorithms for optimization problems in graphs with superlogarithmic treewidth
- Zero knowledge and the chromatic number
- Which problems have strongly exponential complexity?
- Sparsification and subexponential approximation
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- On Hardness of Approximating the Parameterized Clique Problem
- On the Lovász Theta function for Independent Sets in Sparse Graphs
- Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
- Approximation Resistance from Pairwise-Independent Subgroups
- A PCP characterization of NP with optimal amortized query complexity
- Set Partitioning via Inclusion-Exclusion
- Two-query PCP with subconstant error
- Better Inapproximability Results for MaxClique, Chromatic Number and Min-3Lin-Deletion
- Approximation algorithms for NP-complete problems on planar graphs
- Interactive proofs and the hardness of approximating cliques
- Free Bits, PCPs, and Nonapproximability---Towards Tight Results
- Approximating Maximum Clique by Removing Subgraphs
- On independent sets, 2-to-2 games, and Grassmann graphs
- Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut
- From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More
- Approximability of Packing Disjoint Cycles
