Probabilistically checkable proofs and their consequences for approximation algorithms

DOI10.1016/0012-365X(94)00112-VzbMath0824.68087OpenAlexW2060401065MaRDI QIDQ1344618

Hans Jürgen Prömel, Angelika Steger, Stefan Hougardy

Publication date: 6 November 1995

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0012-365x(94)00112-v

zbMATH Keywords

clique numberapproximation algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Arithmetization: A new method in structural complexity theory
• Non-deterministic exponential time has two-prover interactive protocols
• Eigenvalues and expanders
• Explicit constructions of linear-sized superconcentrators
• Optimization, approximation, and complexity classes
• Approximating maximum independent sets by excluding subgraphs
• A still better performance guarantee for approximate graph coloring
• The Knowledge Complexity of Interactive Proof Systems
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• The Complexity of Near-Optimal Graph Coloring
• Algebraic methods for interactive proof systems
• IP = PSPACE
• On the hardness of approximating minimization problems
• The complexity of theorem-proving procedures
• The NP-completeness column: An ongoing guide
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Probabilistically checkable proofs and their consequences for approximation algorithms