April 26, 2005 Lecture 19: Geometric OptimizationGeometric OptimizationPiotr IndykApril 26, 2005 Lecture 19: Geometric OptimizationGeometric Optimization• Minimize/maximize something subject to some constraints• Have seen:– Linear Programming– Minimum Enclosing Ball– Diameter/NN (?)• All had easy polynomial time algorithms for d=2April 26, 2005 Lecture 19: Geometric OptimizationToday• NP-hard problems in the plane– Packing and piercing [Hochbaum-Maass’85]– TSP, Steiner trees, and a whole lot more [Arora’96] (cf. [Mitchell’96])• Best exact algorithms exponential in n• We will see (1+ε)-approximation algorithms that run in poly time for any fixed ε>0 (so, e.g., nO(1/ε)is OK)• Such an algorithm is called a PTASApril 26, 2005 Lecture 19: Geometric OptimizationPacking• Given: a set C of unit disks c1…cn• Goal: find a subset C’ of Csuch that:– All disks in C’ are pair-wise disjoint–|C’|is maximized• How to get a solution of size ≥ (1-ε) times optimum ?April 26, 2005 Lecture 19: Geometric OptimizationAlgorithmkApril 26, 2005 Lecture 19: Geometric OptimizationAlgorithm, ctd.• Impose a grid of granularity k• For each grid cell a– Compute C(a) = the set of disks fully contained in a– Solve the problem for C(a) obtaining C’(a)• Report C’ =union of C’(a) for all cells aApril 26, 2005 Lecture 19: Geometric OptimizationComputing c’(a)• The grid cell a has side length = k• Can pack at most k2disks into a• Solve via exhaustive enumeration →running time O(nk^2)• This also bounds the total running timeApril 26, 2005 Lecture 19: Geometric OptimizationAnalysis• Approximation factor:– Consider the optimal collection of disks C– Shift the grid at random– The probability that a given c∈C not fully contained in some a is at most O(1)/k– The expected number of removed disks is O(|C|/k)– Setting k=O(1/ε) suffices• Altogether: running time nO(1/ε^2)April 26, 2005 Lecture 19: Geometric OptimizationPiercing• Given: a set C of unit disks c1…cn• Goal: find a set P of points such that:–P∩ci≠ Ø for i=1…n–|P|is minimized• How to get a solution of size≤(1+ε) times optimum ?April 26, 2005 Lecture 19: Geometric OptimizationAlgorithmkApril 26, 2005 Lecture 19: Geometric OptimizationAlgorithm, ctd.• Impose a grid G of granularity k• For each cell a– Compute C(a) = the set of disks in Cintersecting a– Solve the problem for C(a) obtaining P(a)• Report P=union of P(a) for all cells aApril 26, 2005 Lecture 19: Geometric OptimizationComputing P(a)• The grid cell a has side length = k• Can pierce C(a) using at most k2points• Sufficient to consider O(n2) choices of piercing points (for all points in P)– Compute arrangement of disks in C(a)– Points in the same cell equivalent• Solve via exhaustive enumeration →running time O(n2k^2)• This also bounds the total running timeApril 26, 2005 Lecture 19: Geometric OptimizationAnalysis• Problem: disks B within distance 1 from the grid boundary • If we eliminated all the occurrences of the disks in Bfrom all C(a)’s, one could pierce the remainder with cost at most OPT(C)• Suffices to show that the cost of piercing B is smallApril 26, 2005 Lecture 19: Geometric OptimizationMore formally• Define B(a)=C(a) ∩ B• The cost of our algorithm is at most ∑aOPT(C(a)) ≤∑aOPT(C(a)-B) + ∑aOPT(B(a)) = OPT(C-B) + ∑aOPT(B(a))•Also, ∑aOPT(B(a)) ≤ 4 OPT(B) , since– Take the optimal piercing T of B– Define T(a)= T ∩ B(a)– We have OPT(B(a)) ≤ |T(a)|– Also, each element of T appears in ≤ 4 sets T(a)–Thus ∑aOPT(B(a)) ≤ ∑a|T(a)| ≤ 4 |T| = 4 OPT(B)April 26, 2005 Lecture 19: Geometric OptimizationAnalysis ctd.• Suffices to show that the cost OPT(B) of optimally piercing B is O(ε OPT(C) ) • Let P be the optimum piercing of C• Shift the grid at random• All disks in B are pierced by P’=P ∩ ( G ⊕ Ball(0,2) )• The probability that a fixed p∈P belongs to P’ is O(1)/k• The expected |P’| of is O(|P|)/k– Setting k=O(1/ε) suffices• Altogether: running time nO(1/ε^2)April 26, 2005 Lecture 19: Geometric OptimizationDynamic programming for TSP• Divide the points using randomly shifted line• Enumerate “all” possible configurations C of crossing points• For each C, solve the two recursive problems• Choose the C that minimizes the costApril 26, 2005 Lecture 19: Geometric OptimizationAnalysis• Structure lemma: for any tour T, there is another tour T’ with cost not much larger than the cost of T, which has only constant number of crossing