Prefer a chat interface with context about you and your work?
Inapproximability of Combinatorial Optimization Problems
This chapter contains sections titled: Introduction Some technical preliminaries Probabilistically checkable proofs Basic reductions Optimized reductions and PCP constructions An overview of known inapproximability results Integrality gap results Other topics Conclusions Prove optimal results for 2-query PCPs Settle the Unique Games Conjecture Prove a strong inapproximability result for Metric TSP …