The Probabilistic Method Idea: to show an object with certain properties exists • generate a random object • prove it has properties with nonzero probability • often, “certain properties” means “good solution to our problem” Last time • set balancing • expanders The Probabilistic Method for Expectations Outline • goal to show exists object of given “value” • give distribution with greater “expected value” • deduce goal Max-Cut: Define• • NP-complete • Approximation algorithms factor 2 • • “expected performance,” so doesn’t really fit our RP/ZPP framework Wiring Sometimes, it’s hard to get hands on a good probability distribution of random answers. Problem formulation • – √n ×√n gate array – Manhattan wiring – boundaries between gates – fixed width boundary means limit on number of crossing wires – optimization vs. feasibility: minimize max crossing number 1� � � – focus on single-bend wiring. two choices for route. – Generalizes if you know about multicommodity max-flow • Linear Programs, integer linear programs – Black box – Good to know, since great solvers exist in practice – Solution techniques in other courses – LP is polytime, ILP is NP-hard – LP gives hints—rounding. IP formulation • – xi0 means xi starts horizontal, xi1 vertical – Tb0 = {i net i through b if xi0}| – Tb1 – IP min w xi0 + xi1 = 1 xi0 + xi1 ≤ w i∈Tb0 i∈Tb1 • Solution ˆi0, ˆ w.x xi1, value ˆ• rounding is Poisson vars, mean ˆw. • For δ < 1 (good approx) Pr[≥ (1 + δ) ˆw/4w] ≤ e−δ2 ˆ• need 2n boundaries, so aim for prob. bound 1/2n2 . • solve, δ = (4 ln 2n2)/ ˆw. So absolute error √8 ˆw ln n• – Good (o(1)-error) if ˆw � 8 ln n – Bad (O(ln n) error) if ˆw = 2 (invoke other chernoff bound) – General rule: randomized rounding good if target logarithmic, not if constant 2� � � � � � � � MAX SAT Define. literals• clauses• • NP-complete random set • achieve 1 − 2−k • very nice for large k, but only 1/2 for k = 1 LP max zj yi + (1 − y1) zj≥ i∈Cj + i∈Cj−Analysis • βk = 1 − (1 − 1/k)k . values 1, 3/4, .704, . . . • Random round yi • Lemma: k-literal clause sat w/pr at least βk zˆj . • proof: – assume all positive literals. – prob 1 − (1 − yi) – maximize when all yi = zˆj /k. – Show 1 − (1 − z/k)k ≥ βk z. – concave, so check equality at z = 0, 1 • Result: (1 − 1/e) approximation (convergence of (1 − 1/k)k ) • much better for small k: i.e. 1-approx for k = 1 LP good for small clauses, random for large. • Better: try both methods. • n1, n2 number in both methods • Show (n1 + n2)/2 ≥ (3/4) zˆj Cj ∈Sk (1 − 2−k )ˆzj• n1 ≥ βk zˆj• n2 ≥ • n1 + n2 ≥ (1 − 2−k + βk )ˆ� 3 ˆzj ≥ 2 zj 3Method of Conditional Probabilities and Expectations Derandomization. • Theory: is P=RP? • practice: avoid chance of error, chance of slow. Conditional Expectation. Max-Cut • Imagine placing one vertex at a time. • xi = 0 or 1 for left or right side • E[C] = (1/2)E[C|x1 = 0] + (1/2)E[C x1 = 1] |• Thus, either E[C x1 = 0] or E[C X1 = 1] ≥ E[C]| |• Pick that one, continue • More general, whole tree of element settings. – Let C(a) = E[C | a]. – For node a with children b, c, either C(b) or C(c) ≥ C(a). • By induction, get to leaf with expected value at least E[C] • But no randomness left, so that is actual cut value. • Problem: how compute node values? Easy. Conditional Probabilities. Set balancing. (works for wires too) • Review set-balancing Chernoff bound • Think of setting item at a time • Let Q be bad event (unbalanced set) • We know Pr[Q] < 1/n. • Pr[Q] = 1/2 Pr[Q | xi0] + 1/2 Pr[Q xi1]| • Follows that one of conditional probs. less than Pr[Q] < 1/n. • More general, whole tree of element settings. – Let P (a) = Pr[Q | a]. – For node a with children b, c, P (b) or P (c) < P (a). – P (r) < 1 sufficient at root r. – at leaf l, P (l) = 0 or 1. • One big problem: need to compute these probabilities! 4Pessimistic Estimators. • Alternative to computing probabilities • three neceessary conditions: – Pˆ(r) < 1 ˆ ˆ – min{Pˆ(b), P (c)} < P (a) – Pˆcomputable Imply can use Pˆinstead of actual. • Let Qi = Pr[unbalanced set i] Let Pˆ(a) = � Pr[Qb | a] at tree node a • Claim 3 conditions. • – HW Result: deterministic O(√n ln n) bias. • • more sophisticated pessimistic estimator for wiring. Oblivious routing • recall: choose random routing. Only 1/N chance of failure Choose N 3 random routines. • • whp, for every permutation, at most 2N 2 bad routes. • given the N 3 routes, pick one at random. • so for any permutation, prob 2/N of being bad. • Advantage: N 3 routes can be stored