6.854 Notes: Approximation Algorithms

Approximation Algorithms What do you do when a problem is NP-complete? • or, when the “polynomial time solution” is impractically slow? • assume input is random, do “expected performance.” Eg, Hamiltonian path in all graphs. Problem: agreeing on good distribution. • run a nonpolynomial (hopefully only slightly) algorithms such as branch and bound. Usually no proven bound on runtime, but sometime can. • settle for a heuristic, but prove it does well enough (our focus) Definitions: • optimization problem, instances I, solutions S(I) with values f : S(I) → R • maximization/minimization: find solution in S(I) maximizing/minimizing f • called OPT(I) • eg bin-packing. instance is set of si ∈ 0, 1, partition so no subset exceeds 1 Techincal assumptions we’ll often make: • assumption: all inputs and range of f are integers/rationals (can’t represent reals, and allows, eg, LP, binary search). • assumption f (σ) is a polynomial size (num bits) number (else output takes too long) • look for polytime in bit complexity NP-hardness • optimization NP-hard if can reduce an NP-hard decision problem to it • (eg, problem of “is opt solution to this instance ≤ k?”) • but use more general notion of turing-reducibility (GJ). Approximation algorithm: • any algorithm that gives a feasible answer • eg, each item in own bin. • of course, want good algorithm. How measure? 1 Absolute Approximations Definition: k-abs approx if on any I, have |A(I) − OP T (I)| ≤ k Example: planar graph coloring. • NP-complete to decide if 3 colorable • know 4-colorable • easy to 5-color • Ditto for edge coloring: Vizing’s theorem says opt is ∆ or (constructive) ∆+1 Known only for trivial cases, where opt is bounded by a constant. Often, can show impossible by “scaling” the problem. • EG knapsack. – define profits pi , sizes si , sack B – wlog, integers. – suppose have k-absolute – multiply all pi by k + 1, solve, scale down. • EG independent set (clique) – k + 1 copies of G Relative Approximation Definitions: • An α-optimum solution has value at most α times optimum for minimization, at least 1/α times optimum for minimization. • an algorithm has approximation ratio α if on any input, it outputs an α-approximate feasilbe solution. • called an α-approximation algorithm How do we prove algorithms have relative approximations? • Can’t describe opt, so can’t compare to it • instead, comparison to computable lower bounds. 2 Greedy Algorithms Do obvious thing at each step. • Hard part is proving it works. • Usually, by attention to right upper/lower bound. Max cut • Upper bound trivial • Max-cut greedy. Min-diameter clustering? • Gonzales’ algorithm. • Distances to existing centers keep dropping • Suppose after k chosen, farthest remaining is distance d • Then OPT ≥ d – k + 1 mutually-distance-d points – some must share a cluster • Now assign each point to closest center • Max distance from center (radius) is d • So max diameter is 2d • 2-approx. Set cover • n items • OPT = k • At each step, can still cover remainder with k sets • So can cover 1/k of remainder Vertex cover: • define problem • suppose repeatedly pick any uncovered edge and cover: no approx ratio • suppose pick uncovered edge and cover both sides: 2-approx • sometime, need to be extra greedy 3 • Explicit attention to where lower bound is coming from—lower bound informs algorithm. Graham’s rule for P ||Cmax is a 2 − 1 m approximation algorithm • explain problem: m machines, n jobs with proc times pj , min proc time. • can also think of minimizing max load of continuously running jobs • use a greedy algorithm to solve • proof by comparison to lower bounds • first lower bound: average load: OPT ≥ 1 m � pj • second lower bound: OPT ≥ max pj • suppose M1 has max runtime L at end • suppose j was last job added to M1 • then before, M1 had load L − pj which was minimum � • so pi ≥ m(L − pj ) + pj • so OPT ≥ L + (1 − 1 m )pj • so L ≤ OPT + (1 − 1 m )pj 1 m )OPT ≤ (2 − Notice: • this algorithm is online, competitive ratio 2 − 1 m • we have no idea of optimum schedule; just used lower bounds. • we used a greedy strategy • tight bound: consider m(m − 1) size-1 jobs, one size-m job • where was problem? Last job might be big • LPT achieves 4/3, but not online • newer online algs achieve 1.8 or so. Approximation Schemes So far, we’ve seen various constant-factor approximations. • WHat is best constant achievable? • Lower bounds: APX-hardness/Max-SNP An approximation scheme is a family of algorithms A
such that • each algorithm polytime • A
achieve 1 +  approx But note: runtime might be awful as function of  4 FPAS, Pseudopolynomial algorithms Knapsack • Dynamic program for bounded profits • B(j, s) = best subset of jobs 1, . . . , j of total size ≤ s. • rounding – Let opt be P . – Scale prices to (n/P )pi  – New opt is it least n/ − n = (1 − )n/ – So find solution within 1 −  of original opt – But table size polynomial • did this prove P = N P ? No • recall pseudopoly algorithms pseudopoly gives FPAS; converse almost true • Knapsack is only weakly NP-hard • strong NP-hardness (define) means no pseudo-poly Enumeration More powerful idea: k-enumeration • Return to P ||Cmax • Schedule k largest jobs optimally • scheduling remainder greedily • analysis: note A(I) ≤ OP T (I) + pk+1 – Consider job with max cj – If one of k largest, done and at opt – Else, was assigned to min load machine, so cj ≤ OP T + pj ≤ OP T + pk+1 – so done if pk+1 small – but note OP T (I) ≥ (k/m)pk+1 – deduce A(I) ≤ (1 + m/k)OP T (I). – So, for fixed m, can get any desired approximation ratio Scheduling any number of machines 5 • Combine enumeration and rounding • Suppose only k job sizes – Vector of “number of each type” on a given machine—gives “machine type” – Only nk distinct vectors/machine types – So need to find how many of each machine type. – Use dynamic program: ∗ enumerate all job profiles that can be completed by j machines in time T ∗ In set if profile is sum of j − 1 machine profile and 1-machine profile – Works because only poly many job profiles. • Use rounding to make few important job types – – – – – – Guess OPT T to with  (by binary search) All jobs of size exceeding T are “large” Round each up to next power of (1 + ) Only O(1/ ln 1/) large types Solve optimally Greedy schedule remainder ∗ If last job is large, are optimal for rounded problem so with  of opt ∗ If last job small, greedy analysis showes we are within  of opt. Relaxations TSP • Requiring tour: no approximation (finding hamiltonian path NP-hard) • Undirected Metric: MST relaxation 2-approx, christofides • Directed: Cycle cover relaxation LP relaxations Three steps • write integer linear program • relax • round Vertex cover. 6 MAX SAT Define. • literals • clauses • NP-complete random setting • achieve 1 − 2−k • very nice for large k, but only 1/2 for k = 1 LP � yi + i∈Cj+ � max (1 − y1 ) ≥ � zj zj 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 ẑj . • proof: – – – – – assume all positive literals. � prob 1 − (1 − yi ) maximize when all yi = ẑj /k. Show 1 − (1 − ẑ/k)k ≥ βk ẑk . check 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) ẑj � • n1 ≥ Cj ∈S k (1 − 2−k )ẑj � • n2 ≥ βk ẑj � �3 • n1 + n2 ≥ (1 − 2−k + βk )ˆ zj ≥ 2 ẑj 7 0.1 Chernoff-bound rounding Set cover. Theorem: � • Let Xi poisson (ie independent 0/1) trials, E[ Xi ] = µ � �µ e
Pr[X > (1 + )µ] < . (1 + )(1+
) • note independent of n, exponential in µ. Proof. • For any t > 0, Pr[X > (1 + )µ] = Pr[exp(tX) > exp(t(1 + )µ)] E[exp(tX)] exp(t(1 + )µ) < • Use independence. E[exp(tX)] = � � E[exp(tXi )] t E[exp(tXi )] = pi e + (1 − pi ) = ≤ 1 + pi (et − 1) exp(pi (et − 1)) exp(pi (et − 1)) = exp(µ(et − 1)) • So overall bound is exp((et − 1)µ) exp(t(1 + )µ) True for any t. To minimize, plug in t = ln(1 + ). • Simpler bounds: – less than e−µ
– less than e 2 2 /3 −µ
/4 for  < 1 for  < 2e − 1. – Less than 2−(1+
)µ for larger . • By same argument on exp(−tX), � Pr[X < (1 − )µ] < bound by e−
2 /2 . Basic application: 8 e−
(1 − )(1−
) �µ • cn log n balls in c bins. • max matches average • a fortiori for n balss in n bins General observations: √ √ • Bound trails off when  ≈ 1/ µ, ie absolute error µ • no surprise, since standard deviation is around µ (recall chebyshev) • If µ = Ω(log n), probability of constant  deviation is O(1/n), Useful if polynomial number of events. • Note similarito to Gaussian distribution. • Generalizes: bound applies to any vars distributed in range [0, 1]. Zillions of Chernoff applications. Wiring. • multicommodity flow relaxation • chernoff bound • union bound 9