Lectures on Proof Verification and Approximation Algorithms
During the last few years, we have seen quite spectacular progress in the area of approximation algorithms: for several fundamental optimization problems we now actually know matching upper and lower bounds for their approximability. This textbook-like tutorial is a coherent and essentially self-contained presentation of the enormous recent progress facilitated by the interplay between the theory of probabilistically checkable proofs and aproximation algorithms. The basic concepts, methods, and results are presented in a unified way to provide a smooth introduction for newcomers. These lectures are particularly useful for advanced courses or reading groups on the topic.
What people are saying - Write a review
We haven't found any reviews in the usual places.
Other editions - View all
3-CNF formula 3SAT 5-close approximation algorithm approximation ratio assume binary string Boolean formula Chapter choose chosen codeword Complete Test compute consider construct coordinate corresponding defined definition denote derandomized deterministic edges encoding equation exists extended verifier finite field function g gadget game G given graph G Hence independent inequality instance integer Lemma length LFKN-TEST linear program logn long code matrix MAX-SNP MAXCLIQUE MAXCUT MAXDlCUT MAXE3SAT MAXEfcSAT maximal MAXSAT nodes non-approximability results nondeterministic Turing machine objective function obtain optimization problems partition PCP-Theorem performance ratio polynomial coding scheme polynomial of degree probabilistic probabilistically checkable proofs probability at least proof of Theorem proof system proof TT prover queries random bits random string random variables randomized algorithm randomized rounding randomly reduction rejects restricted ROBE3SAT satisfying assignment Section semidefinite program solution verifier subset Turing machine vector vertices weights
The Steiner Tree Problem: A Tour Through Graphs, Algorithms, and Complexity
Hans Jürgen Prömel,Angelika Steger
No preview available - 2002
All Book Search results »
Complexity Theory: Exploring the Limits of Efficient Algorithms
No preview available - 2005