Effective Resistance Reducing Flows and ATSP in Optimization

Effective-Resistance-Reducing Flows, Spectrally Thin Trees, and ATSP Nima Anari UC Berkeley Shayan Oveis Gharan Univ of Washington

Asymmetric TSP (ATSP) Given a list of cities and their pairwise distances , satisfying the triangle inequality, ?(?,?) ?(?,?) + ?(?,?). Find the shortest tour that visits all cities exactly once. Asymmetric: ? ?,? ?(?,?). 2

Linear Programming Relaxation [Held-Karp72] ??? ?,?? ?,? ??,? ?.?. ???,?= ???,? ? ? ? ?,? ???,? 1 0 ??,? ? ? ?(OPT tour) ?(OPT LP) max ?(.,.) Integrality Gap: 3

Previous Works Approximation Algorithms log(n) [Frieze-Galbiati-Maffioli 82] .999 log(n) [Bl ser 02] 0.842 log(n) [Kaplan-Lewenstein-Shafrir-Sviridenko 05] 0.666 log(n) [Feige-Singh 07] O(logn/loglogn) [Asadpour-Goemans-Madry-O-Saberi 09] O(1) (planar/bd genus) [O-Saberi 10,Erickson-Sidiropoulos 13] Integrality Gap 2 [Charikar-Goemans-Karloff 06] O(logn/loglogn) [AGMOS 09]. 4

Main Result For any cost function, the integrality gap of the LP relaxation is polyloglog(n). 5

Plan of the Talk Thin Spanning Tree ATSP Max Effective Resistance Spectrally Thin Spanning Tree Our Contribution 6

Thin Spanning Trees Def: Given a k-edge-connected graph ? = (?,?). A spanning tree ? is ?-thin w.r.t. G if ? ?, ? ? |? ?, ? | ? ?, Ideally want ? = ? 1 ? , One-sided unweighted cut-sparsifier No lower-bound on |? ?, ? | ? But even ?<0.99 is interesting ? ? ? Kn 2/n-thin tree Exercise: Show that ??(k-dim cube) has O(1/k) thin tree 7

From Thin Trees to ATSP ?(?) log(?), [AGMOS 09]:If for any log(?)-connected graph ? then the integrality gap of LP is O(? ? ). Furthermore, finding the tree algorithmically gives O(? ? )-approximation algorithm for ATSP. Proof Idea: Max-flow/Min-cut thm. 8

Previous Works: Randomized Rounding Thm: Any k-connected graph G has a ? log(?) thin tree ? Pf. Sample each edge of G, indep, w.p. 2log ? /?. By Karger s cut counting argument, the sampled graph is O(log n k )-thin w.h.p. log(?) ?.log log(?). [AGMOS 09]: Improved the above bound to by sampling random spanning trees. 9

Main Result Any ?-edge-connected graph has an ?(polyloglog ? /?)-thin tree. For any cost function, the integrality gap of the LP Relaxation is polyloglog(n). 10

In Pursuit of Thin Trees Beyond Randomized Rounding 11

Graph Laplacian Let ??,?= 1? 1? For ? ?, let ??= (?,?) ???,???,? ?, 2 1 2 0 1 1 0 2 1 0 1 1 0 1 1 2 ??= Laplacian Quadratic Form: 2, ????? = (?,?) ??? ?? E.g., ???1?= ? ?, ? 1? 12

Spectrally Thin Spanning Trees Def: A spanning tree ? is ?-spectrally thin w.r.t. G if ?? ? ?? ?.?. ????? ? ?????, ? Why? Generalizes (combinatorial) thinness. ?-spectral thinness implies ?-combinatorial thinness ? ?,1? ???1? ?1? ???1? Testable in polynomial time. Compute max eigenvalue of 1/2???? 1/2 ?? 13

A Necessary Condition for Spectral Thinness Lem: The spectral thinness of any T is at least max ? ?Reff?(?), where ??? 1??,?, Reff??,? = ??,? ??,?= 1? 1?. Pf. If T is ?-spectrally thin, then any subgraph of T is ?- spectrally thin, so ? ?, ???? Reff??,? is the spectral thinness of ? = {?,?}. ?? ?= ?? ? ?? 1?? ?. ??? 14

A k-con Graph with no Spectrally Thin Tree For any spanning tree, T, ? ?Reff?? 1 ?2 max ?. 1A k edges Reff ? 1 ?2 ? 1A k edges n/k vertices 15

A Sufficient Condition for Spectral Thinness [Marcus-Spielman-Srivastava 13,Harvey-Olver 14]: Any G has an ?(max ? ?Reff?(?))-spectrally thin tree. So, any edge-transitive k-connected graph (e.g., ??) has an O(1/k)-(spectrally) thin tree. 16

Spectrally Thin Trees (Summary) k-edge connectivity O(1/k)-combinatorial thin tree ? Reff?? 1/? for all ? ? O(1/k)-spectrally thin tree [MSS13] 17

https://encrypted-tbn3.gstatic.com/images?q=tbn:ANd9GcT0yRf03PDE7LGP0Imo6GC-hf-U-MA8QJM4_PiAhavmO9db59tohttps://encrypted-tbn3.gstatic.com/images?q=tbn:ANd9GcT0yRf03PDE7LGP0Imo6GC-hf-U-MA8QJM4_PiAhavmO9db59to Our Approach 18

Main Idea Symmetrize L2 structure of G while preserving its L1 structure 19

An Example n/k vertices Reff?+?? 1/ ? for all black edges 20

An Observation An Application of [MSS 13]:If for any cut (?, ?), avg ? (?, ?) Reff?? ?, Then G has a ? ? -spectrally thin tree. 21

Main Idea ? ?Reff?+?(?) ?(1 Find a ``graph D s.t. max ?) and ???1? 1? ???1?. ?? ??? i.e., ?, 1? Bypasses Spectral Thinness Barrier. D+G has a spectrally thin tree and any spectrally thin tree of G+D is (comb) thin in G. 22

An Impossibility Theorem Thm: There is a k-connected graph G, s.t., for any 0 ? ???, max ? ?Reff?? = 1 . 23

Proof Overview G has ?( comb thin tree 1 ?)- k-connected graph G for ? log(?) Note we may have ? ?, ? |? ?, ? | Main D is not a graph Tech Thm 0 ? ???, ? ?, F is (?)-connected, max ? + ? has ? spectrally thin tree A General. of [MSS 13] 1 ? - ? ?Reff?? = ?( 1 ?) 24

Thin Basis Problem Thm: Given a set of vectors ?? ? ? ? s.t. ????? ? , 2 ?. max ? ? ?? ? ? ? disjoint bases, ...... , there are 1 then there is a basis ?? ? ? If s.t. d Linearly independent set of vectors ? ?????? ?(?). 25

Proof Overview G has ?( comb thin tree 1 ?)- k-connected graph G for ? log(?) Main Tech Thm 0 ? ???, ? ?, F is (?)-connected, max ? + ? has ? spectrally thin tree A General. of [MSS 13] 1 ? - ? ?Reff?? = ?( 1 ?) 26

A Weaker Goal: Satisfying Degree Cuts Thm: Given a k-connected graph, 0 ? ???, s.t., for all v, ?? ? ?Reff?? ?, for ? = ?( 1 ?). Let ? = ?:Reff?e 2? , then by Markov Ineq, ? ? ? ? 2, for all v. By [MSS13] implies existence of ?(1 ?)-thin edge covers. 27

A Convex Program for Optimum D Recall convexity of matrix inv 1 2? + ? 1 1 2? 1+1 ??? max ? ??? ? ?Reff?? 2? 1 Has exp. many constraints: 1? ?.?. ? ??? ??1? 1? ???1? If write ? ??, then optimum ? is ?? ? 0 Thm: For any k-connected graph, the optimum is ?(1/?). Proof Idea: The dual is ?(1/?). 28

Main Result Any ?-edge-connected graph has an ?(polyloglog(?)/k)-thin tree. For any cost function, the integrality gap of the LP Relaxation is polyloglog(n). 29

Conclusion Main Idea: Symmetrize L2 structure of G while preserving its L1 structure Tools: Interlacing polynomials/Real Stable polynomials Convex optimization Graph partitioning High dimensional geometry 30

Future Works/Open Problems Algorithmic proof of [MSS 13] and our extension. Existence of C/k thin trees and constant factor approximation algorithms for ATSP. Subsequent work: Svensson designed a 27-app algorithm for ATSP when c(.,.) is a graph metric. 31