Better Inapproximability Results for MaxClique, Chromatic Number and Min-3Lin-Deletion

DOI10.1007/11786986_21zbMath1223.68047OpenAlexW1483324665MaRDI QIDQ3613762

Subhash A. Khot, Ashok Kumar Ponnuswami

Publication date: 12 March 2009

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/11786986_21

Mathematics Subject Classification ID

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

Related Items (15)

Inapproximability of maximum biclique problems, minimum \( k\)-cut and densest at-least-\( k\)-subgraph from the small set expansion hypothesis ⋮ On the Lovász Theta Function for Independent Sets in Sparse Graphs ⋮ On approximating string selection problems with outliers ⋮ Competitive and collaborative influence in social networks ⋮ From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More ⋮ Approximability of sparse integer programs ⋮ Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with $2^{(\log {n})^{\Omega(1)}}$ Colors ⋮ Finding large cliques in sparse semi-random graphs by simple randomized search heuristics ⋮ Unnamed Item ⋮ New tools and connections for exponential-time approximation ⋮ Unnamed Item ⋮ Parameterized inapproximability of independent set in \(H\)-free graphs ⋮ Unnamed Item ⋮ On the approximability of the maximum agreement subtree and maximum compatible tree problems ⋮ Improved Dynamic Graph Coloring

This page was built for publication: Better Inapproximability Results for MaxClique, Chromatic Number and Min-3Lin-Deletion