Report

Doubling dimension and the traveling salesman problem Yair Bartal Lee-Ad Gottlieb Robert Krauthgamer Hebrew University Hebrew University Weizmann Institute Traveling salesman problem Definition: Given a set of cities (points) find a minimum tour that visits each point Classic, well-studied NP-hard problem [Karp ‘72; Papadimitriou, Vempala ‘06] Mentioned in a handbook from 1832! Common benchmark for optimization methods Many books devoted to TSP… Other variants Closed tour Multiple tours Etc… Optimal tour 2 Traveling salesman problem Some additional assumptions on distances Symmetric d(x,y) = d(y,x) Metric Triangle inequality: d(x,y) + d(y,z) ≤ d(x,z) Easy 2-approximation via MST Since OPT ≥ MST MST 3 Traveling salesman problem Some additional assumptions on distances Symmetric d(x,y) = d(y,x) Metric Triangle inequality: d(x,y) + d(y,z) ≤ d(x,z) Easy 2-approximation via MST Since OPT ≥ MST Can do better… Christophides: MST + Matching ≤ 1½ OPT MST 4 Euclidean TSP Sanjeev Arora [A. ‘98] and Joe Mitchell [M. ‘99] : Euclidean TSP with fixed dimension admits a PTAS (1+Ɛ)-approximate tour In time n(log n)Ɛ-Ỡ(d) (Easy extension to other norms) They were awarded the 2010 Gödel Prize for this discovery 5 Euclidean TSP To achieve a PTAS, two properties were assumed Euclidean space Fixed dimension Are both these assumptions required? Fixed dimension is necessary Hardness: No PTAS for (log n)-dimensions [Trevisan ’00] Is Euclidean necessary? A PTAS for metric space? Problem: Arbitrary metric space includes high-dimension Euclidean space... What about metric spaces with low intrinsic dimension? 6 Doubling Dimension Definition: Ball B(x,r) = all points within distance r from x. The doubling constant (of a metric M) is the minimum value >0 such that every ball can be covered by balls of half the radius First used by [Assoud ‘83], algorithmically by [Clarkson ‘97]. The doubling dimension is ddim(M)=log(M) [Gupta,Krauthgamer,Lee ‘03] A metric is doubling if its doubling dimension is constant Packing property of doubling spaces A set with diameter D and min. inter-point distance a, contains at most (D/a)O(ddim) points Here ≤7. 7 Applications of doubling dimension Nearest neighbor search Spanner construction, routing 1 1 2 2 1 1 1 [Har-Peled, Mendel ’06; Bartal, G., Roditty, Kopelowitz, Lewenstein ’11] [G., Krauthgamer, ’11; Bartal, Recht, Schulman ‘11] Machine learning H Dimension reduction [G., Roditty ’08a, ’08b; Elkin, Solomon ‘12a, ‘12b; Abraham, Gavoille, Goldberg, Malkhi ‘05] G Distance oracles [Krauthgamer, Lee ’04; Har-Peled, Mendel ’06; Beygelzimer, Kakade, Langford ’06; Cole, G. ‘06] [Bshouty, Yi, Long ‘09; G., Kontorovich, Krauthgamer ’10, ‘12; ] Extension to nearly-doubling spaces [G., Krauthgamer ‘10] 8 PTAS for metric TSP? Does TSP on doubling metrics admit a PTAS? Arora and Mitchell made strong use of Euclidean properties “Most fascinating problem left open in this area” James Lee, tcs math blog, June ‘10 Some attempts Quasi-PTAS QPTAS for metric with neighborhoods [Talwar ‘04] (First description of problem) [Mitchell ’07; Chan, Elbassioni ‘11] Subexponential-TAS, under more general growth assumption [Chan, Gupta ‘08] 9 PTAS for metric TSP? Does TSP on doubling metrics admit a PTAS? Yes! (1+Ɛ)-approximate tour 2 In time: n2O(ddim) 2Ɛ-Ỡ(ddim) 2O(ddim ) log½n Euclidean: n (log n)Ɛ-Ỡ(d) We’ll jump right in to the construction 10 Metric partition Starting point – a quadtree like hierarchy [Talwar ‘04, Bartal ‘96] 11 Metric partition Starting point – a quadtree like hierarchy [Talwar ‘04, Bartal ‘96] Random radius Ri = [2i, 2·2i] Arbitrary center point, ordering 12 Metric partition Starting point – a quadtree like hierarchy [Talwar ‘04, Bartal ‘96] 13 Metric partition Starting point – a quadtree like hierarchy [Talwar ‘04, Bartal ‘96] Random radius Ri-1 = [2i-1, 2·2i-1] Arbitrary center point Caveat: logn hiearchical levels suffice Ignore tiny distances < 1/n2 14 Metric TSP Definition: A tour is (m,r)-light on a hierarchy if it enters all cells (clusters) At most r times Only via m portals Portals are 2i-1/M –net points m = MO(ddim) 2i-1/M 15 Metric TSP Theorem [Arora ‘98,Talwar ‘04]: Given a partition The best (m,r)-light tour on the partition can be computed exactly mr O(ddim) nlogn time Via simple dynamic programming Join tours for small clusters into tour for larger cluster 16 Metric TSP Our contribution Theorem: Given an optimal tour T, there exists a partition with (m,r)-light tour T’ M = ddim logn/Ɛ m = MO(ddim) = (logn/Ɛ)Ỡ(ddim) r = Ɛ-O(d) loglogn Length of T’ is within (1+Ɛ) factor of the length of T 17 Metric TSP Our contribution Theorem: Given an optimal tour T, there exists a partition with (m,r)-light tour T’ M = ddim logn/Ɛ m = MO(ddim) = (logn/Ɛ)Ỡ(ddim) r = Ɛ-O(d) loglogn Length of T’ is within (1+Ɛ) factor of the length of T If the partition were known, then T’ could be found in time mr O(ddim) n logn = n 2Ɛ-Ỡ(ddim) loglog2n 18 Metric TSP Our contribution Theorem: Given an optimal tour T, there exists a partition with (m,r)-light tour T’ Length of T’ is within (1+Ɛ) factor of the length of T If the partition were known, then T’ could be found in time M = ddim logn/Ɛ m = MO(ddim) = (logn/Ɛ)Ỡ(ddim) r = Ɛ-O(d) loglogn mr O(ddim) n logn = n 2Ɛ-Ỡ(ddim) loglog2n It remains only to prove the Theorem, and to show how to find the partition 19 Metric TSP Modify a tour to be (m,r)-light Part I: Focus on m (i.e. net points) [Arora ‘98, Talwar ‘04] Move cut edges to be incident on net points Ri-1/M 20 Metric TSP Modify a tour to be (m,r)-light Part I: Focus on m (i.e. net points) [Arora ‘98, Talwar ‘04] Move cut edges to be incident on net points Expected cost to edge At the (i-1)-level, radius Ri-1~2i-1 Expected cost ~ (Ri-1/M)(ddim/Ri-1) = ddim/M = Ɛ/logn (assuming edge length 1) Ri-1/M Expected cost to edge over all levels: logn * Ɛ/logn = Ɛ (1+Ɛ)-approximate tour 21 Metric TSP Modify a tour to be (m,r)-light Part II: Focus on r (i.e. number of crossing edges) Reduce number of crossings 22 Metric TSP Modify a tour to be (m,r)-light Part II: Focus on r (i.e. number of crossing edges) Reduce number of crossings Patchings [Arora ‘98]: Reroute edges back into cluster Cost: ~ length of tour on the patched endpoints ~ MST of these points 23 MST in doubling spaces Bound the weight of MST in doubling space [Talwar ‘04]: For any r-point set S MST(S) = Rr1-1/ddim « Rr Per point cost = R/r1/ddim 2R 24 Metric TSP Modify a tour to be (m,r)-light – Part II Focus on r (i.e. number of crossing edges) Reduce number of crossings Expected cost to edge At the (i-1)-level, radius Ri-1~2i-1 Probability edge is patched ≤ Probability edge is cut (Ri-1/r1/ddim)(ddim/Ri-1) = ddim/r1/ddim 2R 25 Metric TSP Modify a tour to be (m,r)-light – Part II Focus on r (i.e. number of crossing edges) Reduce number of crossings Expected cost to edge At the (i-1)-level, radius Ri-1~2i-1 Probability edge is patched ≤ Probability edge is cut (Ri-1/r1/ddim)(ddim/Ri-1) = ddim/r1/ddim As before, want this term to be equal to Ɛ/logn So we get a contribution of Ɛ over logn levels Could take r = (ddim logn/Ɛ)ddim But dynamic program runs in time mr – QPTAS! [Talwar ‘04] Challenge: smaller value for r 2R 26 Metric TSP Key observation: Space can be decomposed into sparse neighborhoods Consider an (i-1)-level ball If the local tour weight inside is at least Ri-1/Ɛ “Dense” ball Ball can be removed, each subproblem solved separately 27 Metric TSP Key observation: Space can be decomposed into sparse neighborhoods Consider an (i-1)-level ball If the local tour weight inside is at least Ri-1/Ɛ “Dense” ball Ball can be removed, each subproblem solved separately Cost to join tours: only Ri-1 28 Metric TSP Sparse decomposition: Search hierarchy bottom-up for “dense” balls. Remove “dense” ball Ball is composed of sparse subballs So it’s barely dense Recurse on remaining point set How do we know the local weight of the tour in a ball? Can be estimated using the local MST Modulo some caveats, error terms… OPT Ʌ B(u,R) = O(MST(S)) B(u,3R) Ʌ OPT = Ω(MST(S)) -Ɛ-O(ddim) R 29 Metric TSP Suppose a tour is q-sparse with respect to hierarchy Cluster formed by cuts from many levels Every R-ball contains weight Rq (for all R=2i) Expectation: Random R-ball cuts weight Rq/R = q Expectation: q cuts per level If r = q 2loglogn Expectation: (i-1)-level patching includes cuts from 2loglogn higher levels Charge patching to edges in top loglogn levels Ri-1/M Cut Pr: (ddim/Ri+loglogn) = (ddim/Ri-1 logn) 30 Metric TSP Modify a tour to be (m,r)-light – Part II Focus on r (i.e. number of crossing edges) Expected cost to edge Reduce number of crossings At the (i-1)-level, radius Ri-1~2i-1 Probability edge is patched ≤ Probability edge is cut (Ri-1/r1/ddim)(ddim/Ri-1logn) = ddim/logn r1/ddim 2R As before, want this term to be equal to Ɛ/logn Can take r = (ddim/Ɛ)ddim PTAS! 31 Metric TSP Outstanding problem: Previous analysis assumed ball cuts only q edges True in expectation… Not good enough Solution: try many hierachies choose logn random radii for each ball Then some hierarchy has balls which cut only q edges Drives up runtime of dynamic program Thank you! Ri-1/M 32