The Nonapproximability of Non-Boolean Predicates
From MaRDI portal
Publication:4652625
DOI10.1137/S0895480100380458zbMath1087.68038MaRDI QIDQ4652625
Publication date: 28 February 2005
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Randomized algorithms (68W20)
Related Items
Supermodular functions and the complexity of MAX CSP ⋮ Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs ⋮ Unnamed Item ⋮ More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP ⋮ The Quest for Strong Inapproximability Results with Perfect Completeness
This page was built for publication: The Nonapproximability of Non-Boolean Predicates