Improved non-approximability results
From MaRDI portal
Publication:2817610
DOI10.1145/195058.195129zbMath1344.68094MaRDI QIDQ2817610
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
68Q25: Analysis of algorithms and problem complexity
05C15: Coloring of graphs and hypergraphs
05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
Related Items
On point covers of \(c-\)oriented polygons, The asymmetric median tree. --- A new model for building consensus trees, Novel evolutionary models and applications to sequence alignment problems, Zero knowledge and the chromatic number, Label placement by maximum independent set in rectangles, Compact location problems, Interactive and probabilistic proof-checking, Fast stabbing of boxes in high dimensions, Clique is hard to approximate within \(n^{1-\epsilon}\), Approximation algorithms for general parallel task scheduling, On weighted vs unweighted versions of combinatorial optimization problems, Algebraic testing and weight distributions of codes., Towards optimal lower bounds for clique and chromatic number., The complexity of approximating a nonlinear program, Simulating BPP using a general weak random source, Improved non-approximability results for minimum vertex cover with density constraints, Breaking the ε-Soundness Bound of the Linearity Test over GF(2)
