Improved non-approximability results

DOI10.1145/195058.195129zbMath1344.68094OpenAlexW1991006936MaRDI QIDQ2817610

Madhu Sudan, Mihir Bellare

Publication date: 1 September 2016

Published in: Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/195058.195129

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (29)

Algebraic testing and weight distributions of codes. ⋮ Towards optimal lower bounds for clique and chromatic number. ⋮ An \(\tilde{O}(n^{3/14})\)-coloring algorithm for 3-colorable graphs ⋮ Improved approximations of independent sets in bounded-degree graphs ⋮ Recent results in hardness of approximation ⋮ Facility dispersion and remote subgraphs ⋮ Some recent strong inapproximability results ⋮ The complexity of approximating a nonlinear program ⋮ Novel evolutionary models and applications to sequence alignment problems ⋮ Simulating BPP using a general weak random source ⋮ Compact location problems ⋮ Compact location problems with budget and communication constraints ⋮ Fault detection tests for stuck-at faults on parity counter inputs ⋮ Complexity and approximability of certain bicriteria location problems ⋮ From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More ⋮ Improved non-approximability results for minimum vertex cover with density constraints ⋮ Breaking the ε-Soundness Bound of the Linearity Test over GF(2) ⋮ On point covers of \(c-\)oriented polygons ⋮ Short Locally Testable Codes and Proofs: A Survey in Two Parts ⋮ The asymmetric median tree. --- A new model for building consensus trees ⋮ Integrality gap of the vertex cover linear programming relaxation ⋮ Short Locally Testable Codes and Proofs ⋮ Zero knowledge and the chromatic number ⋮ Label placement by maximum independent set in rectangles ⋮ Interactive and probabilistic proof-checking ⋮ Fast stabbing of boxes in high dimensions ⋮ Clique is hard to approximate within \(n^{1-\epsilon}\) ⋮ On weighted vs unweighted versions of combinatorial optimization problems ⋮ Approximation algorithms for general parallel task scheduling

This page was built for publication: Improved non-approximability results