Inapproximability of Combinatorial Optimization Problems
Luca Trevisan · 2014
This chapter focuses on approximation algorithms, which are algorithms of the second kind with a provably good worst-case ratio between the value of the solution found by the algorithm and the true optimum. It devotes results that follow from conjectural forms of the probabilistically checkable proof (PCP) theorem, such as the Unique Games conjecture. The chapter focuses on techniques used to prove inapproximability results, and reviews what is known for various fundamental problems. The chapter discusses integrality gap results for various optimization problems. After approaching the field from the perspectives of techniques and of results for specific problems, it discusses a number of alternative questions that have been pursued. The chapter also discusses the study of complexity classes of combinatorial optimization problems, of relations between average-case complexity and inapproximability, and of the issue of witness length in PCP constructions.