15-854 Approximation and Online Algorithms 01/31/00 * About the presentations * routing with randomized rounding * Chernoff bounds * A quick intro to approximation hardness results ======================================================================= Routing with Randomized Rounding --> see notes from last time. Chernoff bounds --> see notes from last time. Quick intro to approximation hardness results. In early 90's, a sequence of results on Interactive Proofs, 2-Prover IP, Probabilistically Checkable Proofs, led to the following result. There exists a poly time transformation T from 3CNF to 3CNF, and a constant epsilon such that: if phi is satisfiable then phi' = T(phi) is satisfiable. If phi is not satisfiable, then at most a 1 - epsilon fraction of the clauses of phi' are simultaneously satisfiable. Several points: (1) This means that it is NP-hard to approximate MAX-3SAT to better than 1-epsilon. In fact, even hard to approximate the value of the optimal solution. The approx version of a decision question is a "promise problem". Given the promise that the value of the optimal solution is < x or > a*x, determine which case it is. (2) Can see connection to "integrality gap" here, since if you have a fractional relaxation of some problem with integrality gap alpha (the worst case ratio between the optimal integral and optimal fractional solutions) then you automatically can approx the value to ratio alpha. In fact, for the routing problem, the current state of knowledge is pretty bizarre: there's no known example where the optimal integral solution is more than (opt fractional)+2. So, conceivably the algorithm "add 2 to floor(opt fractional)" approximates the value of the optimal solution to an additive +2. (3) Notice that unlike with exact solutions, we don't have approx-search reducing to approx-decision. Even if the above *did* always find a value within +2 of the optimal, it's not at all clear how to use that to find a solution within +2 of optimal. (4) These approx hardness results come out of notion of "probabilistically checkable proofs". Idea is you want to write out a proof of some statement (like that a given formula is satisfiable) that can be checked by only examining a small number of bits of the proof. Notice that the transformation T does this for us: to prove that phi is satisfiable, we write out a satisfying assignment for T(phi). [Note: T also gives a polytime way to take an assignment for phi and turn it into an assignment for T(phi)]. A checker will just pick O(1/epsilon) random clauses in T(phi) and check that our assignment satisfies them. The point is that if phi was *not* satisfiable then since T(phi) is not even approximately satisfiable, we would not be able to write down any assignment that this checker would have accepted with reasonable probability. [There's a subtle but unimportant thing here: if phi *was* satisfiable, we would have been able to write an "almost correct" assignment for T(phi) if we wanted to. I.e., we can write "almost correct" proofs to correct theorems, we just can't write "almost correct" proofs to incorrect theorems this way]. Sometimes called "holographic proofs". If time remaining: Clique approx hardness to n^{epsilon}