Report

Approximating Graphic TSP by Matchings Tobias Mömke and Ola Svensson KTH Royal Institute of Technology Sweden Travelling Salesman Problem • Given – n cities – distance d(u,v) between cities u and v • Find shortest tour that visits each city once 1 1 2 2 1 1 4 2 1 3 Value = 1+2+1+1 = 5 Classic Problem 1800’s 1930’s 50’s 60’s 70’s 80’s 90’s 00’s 2392 cities13509 cities •G.AnDantzig, optimal ofform 120Hamilton cities (West) Germany William General R.tour Fulkerson, Rowan of and TSPS.of gets Johnson and popular Thomas publish and Penyngton is a method promoted Kirkman forbysolving the S. Arora and J. S. studied B. Mitchell publish related TSPmathematical andasolve a problems PTAS for Euclidian49-city TSP instance to optimality Major open problem to understand approximabilityalgorithm of metric TSP: • Christofides publishes the famous the 1.5-approximation C. H. Papadimitriou and S. Vempala: • NP-hard toproposes approximate better than 220/219 Held-Karp a very successful heuristic for calculating NP-hard to approximate 220/219 Proctor and Gamble ran awithin contest for solving a TSP instance on 33 cities a lower boundalgorithm on a tour still best • Christofides’ 1.5-approximation Applegate, Cook, •• The lowerBixby, boundChvatal, coincides withand theto value a linear program known as Held-Karp relaxation is conjectured haveofintegrality gap of 4/3 Karl Menger Helsgaun find the shortest tour of Whitney Hassler Merrill Flood Hamilton Kirkman 24978 cities Held-Karp in Sweden or Subtour Elimination relaxation http://www.tsp.gatech.edu/ Graphic TSP (graph-TSP) • Given an unweighted graph G(V,E), • find spanning the shortest Eulerian tour with multigraph respectwith to distances minimum #edges Length = 4n/3 -1 1 #edges = 4n/3 -1 1 4 Important Special Case • Natural problem to find smallest Eulerian subgraph – Studied for more than 3 decades • Easier to study than general metrics but hopefully shed light on them – Still APX-hard – Worst instances for Held-Karp lower bound are graphic – Any difficult instance to Held-Karp lower bound is determined by a weighted graph with at most 2n-3 edges – Until recently, Christofides best approximation algorithm Recent Advancements on graph-TSP 2000 2005 2010 Boyd, Gharan, Sitters, van der &Star & Stougie Oveis Saberi Singh give a give a (1.5-ε)-approximation algorithm for graph-TSP Major open problem to understand approximability of metric TSP: 4/3-approximation algorithm forthe cubic graphs Gamarnik, Lewenstein & Sviridenko give a -• First improvement overbetter Christofides NP-hard to approximate than 220/219 -7/5-approximation Similar to Christofides, but instead of starting with a minimum algorithm for subcubic graphs 1.487-approximation for cubic graphs • Christofides’ 1.5-approximation still best connected MST they sample onealgorithm from thealgorithm solution of3-edge Held-Karp relaxation -Conjecture: Analysis requires several novel ideas, like structure of almost • Held-Karp relaxation is conjectured to have integrality gap of 4/3 minimum cuts subcubic 2-edge connected graphs has a tour of length 4n/3 -2/3 Our Results A 1.461-approximation algorithm for graph-TSP Based on techniques used by Frederickson & Ja’Ja’82 and Monma, Munson & Pulleyblank’90 + novel use of matchings: instead of only adding edges to make a graph Eulerian we allow for removal of certain edges Subcubic 2-edge-connected graph has a tour of length at most 4n/3 – 2/3 A 4/3-approximation algorithm for subcubic/claw-free graphs (matching the integrality gap) Outline • Held-Karp Relaxation • Given a 2-vertex connected graph G(V,E) find a spanning Eulerian graph with at most 4/3|E| edges • Introduce removable edges and prove Subcubic 2-edge-connected graph has a tour of length at most 4n/3 – 2/3 • Comments on general graphs Held-Karp Relaxation • A variable x{u,v} for each pair u,v of cities Very well studied: • Any extremepoint has support consisting of at most 2n-3 edges • Restriction to 2-vertex-connected graphs is w.l.o.g. Eulerian subgraph of 2-VC graph Frederickson & Ja’Ja’82 and Monma, Munson & Pulleyplank’90 1. Use An edge gadgets is intoMmake with graph probability cubic 1/3 2. Sample Expected perfect size ofmatching M U E is 4/3|E| M so that each edge is taken with probability 1/3 application Edmond’s matching polytope) 3. A(Simple 2-VC graph has aoftour of sizeperfect 4/3|E| 3. Return graph with edge set Using Matchings to Remove Edges First Idea 1. Observation: Expected sizeremoving of returned graph: an Eulerian edge from the matching will still result in even degree vertices 2. If it stays connected we will again have an Eulerian graph 3. Same algorithm as before but return Using Matchings to Remove Edges Second Idea 1. Use structure of perfect matchings to increase the set R of removable edges 2. If it stays connected we will again have an Eulerian graph 3. Define a “removable pairing” • Pair of edges: only one edge in each pair can be removed by a matching • Graph obtained by removing removable edges such that at most one edge in each pair is removed is connected R contains all back-edges and tree-edges paired with a back-edge If G has degree at most 3 then size of R is 2b-1 Using Matchings to Remove Edges Second Idea 1. Same We have algorithm that |R|as=before 2b -1 and but |E| return = n-1 + b and thus Result for Graphs of Max Degree 3 Subcubic 2-edge-connected graph has a tour of length at most 4n/3 – 2/3 A 4/3-approximation algorithm for subcubic/claw-free graphs (matching the integrality gap) • Matchings can be used to also remove edges • Used structure to increase number of removable edges “removable pairing” General Case • In degree 3 instances each back-edge is paired with a tree edge • In general instance this might not be possible • LP prevents this situation: • Min Cost circulation flow where the cost makes you pay for this situation • Analyze by using LP extreme point structure Final Result Christofides Our 1.0 1.02 1.04 1.06 1.08 1.1 A 1.461-approximation algorithm for graph-TSP Summary • Novel use of matchings – allow us to remove edges leading to decreased cost • Bridgeless subcubic graphs have tour of size 4n/3 - 2/3 – Tight analysis of Held-Karp for these graphs • 1.461-approximation algorithm for graph-TSP Open Problems • Find better removable pairing and analysis – If LP=n is there always a 2-vertex connected subgraph of degree 3? • Removable paring straight forward to generalize to any metric – However, finding one remains open • One idea is to sample extremepoint, for example: – Sample two spanning trees with marginals xe such that all edges are removable => 4/3–approximation algorithm