Exploring Approximation Algorithms for TSP Variants
Delve into the world of Traveling Salesman Problem (TSP) and its variants, encompassing Symmetric TSP, Asymmetric TSP, and cutting-edge approximation algorithms. Understand the intricacies of finding Hamiltonian cycles efficiently and the ongoing research in combinatorial optimization. Discover the allure of TSP, its challenges, and the pursuit of optimal solutions in this captivating field.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Approximation Algorithms for TSP Mohit Singh McGill University (in lieu of Amin Saberi)
Traveling Salesman Problem What is TSP? TSP is perhaps the most well-known combinatorial optimization problem Gutin and Punnen, TSP book Why do people work on TSP? It belongs to the most seductive problems in combinatorial optimization, thanks to a blend of complexity, applicability, and appeal to imagination - Schrijver, Combinatorial Optimization.
Contest by Proctor and Gamble.
TSP and its variants Given a complete graph G with metric d Goal: Find a Hamiltonian cycle of shortest length. Symmetric TSP (STSP) Asymmetric TSP (ATSP) d(u,v) need not be equal to d(v,u) d(u,v)=d(v,u) for all u,v log n approximation [FGM 82] 3/2-approximation [Christofides 76] Conjecture: O(1)-approximation Conjecture: 4/3-approximation PTAS for Euclidean Metric[Arora], planar metric[GKP].
TSP and its variants Given a complete graph G with metric d Goal: Find a Hamiltonian cycle of shortest length. Symmetric TSP (STSP) Asymmetric TSP (ATSP) log n approximation [FGM 82] 3/2-approximation [Christofides 76] Conjecture: O(1)-approximation Conjecture: 4/3-approximation [Asadpour, Gharan, Goemans, Madry, Saberi 10] : O(log n/log log n)- approximation
TSP and its variants Given a complete graph G with metric d Goal: Find a Hamiltonian cycle of shortest length. Symmetric TSP (STSP) Asymmetric TSP (ATSP) log n approximation [FGM 82] 3/2-approximation [Christofides 76] Conjecture: O(1)-approximation Conjecture: 4/3-approximation [Asadpour, Gharan, Goemans, Madry, Saberi 10] : O(log n/log log n)- approximation [Gharan, Saberi, S 10]: 3/2- approximation for graphical TSP.
Linear Program for STSP Subtour Elimination LP [Held and Karp 70] min ( ) d e x e e t s . . = ( ( )) 2 x v v V ( ( )) 2 x S 0 S V x e e LP can be solved efficiently using the ellipsoid algorithm. Separation Oracle: Mincut Algorithm!
Linear Program for ATSP Subtour Elimination LP [Held and Karp 70] min ( ) d e x e e t s . . = = out in ( ( )) ( ( )) 1 x v x 1 v v V out ( ( )) x S S V 0 x e e LP can be solved efficiently using the ellipsoid algorithm. Separation Oracle: Mincut Algorithm!
LP and Spanning tree polyhedron Can write x* as a convex combination of spanning trees. = = * , , 1 0 x iT i i i i i Select a spanning tree F = Ti s.t. entropy is maximized. i max log i i e = = * e . . t s Pr [e F] x i T i i = , 1 0 i i
Max entropy distributions Lemma[AGGMS]: Max entropy distributions are equivalent to a uniform spanning tree distribution. Easy to Sample. Can use many properties of uniform random spanning trees. Indicator random variables Xe are negatively associated [Feder, Mihail]. Pr[Xe=1|Xf=1]<=Pr[Xe=1] Implies concentration (Chernoff bounds)
Christofides* Algorithm Sample a spanning tree F from max-entropy distribution. Return the cheapest Eulerian augmentation of F STSP : matching over odd degree nodes of F
Christofides* Algorithm Sample a spanning tree F from max-entropy distribution. Return the cheapest Eulerian augmentation of F STSP : matching over odd degree nodes of F ATSP: circulation problem with demand=imbalance of indegree/outdegree Theorem[AGGMS]: Christofides* is O(log n/log log n)- approximation for ATSP Conjecture[GSS]: Christofides* is (3/2- )-approximation for STSP.
Christofides* Algorithm Sample a spanning tree F from max-entropy distribution. Return the cheapest Eulerian augmentation of F STSP : matching over odd degree nodes of F ATSP: circulation problem with demand=imbalance of indegree/outdegree Theorem[AGGMS]: Christofides* is O(log n/log log n)- approximation for ATSP Theorem[GSS]: Christofides** is (3/2- )-approximation for graphical STSP. d(u,v)=shortest path between u and v in an unweighted graph
ATSP Eulerian Augmentation (Circulation Problem) Question: How closely does T approximate every cut of (G,x*). What is the smallest s.t. . | ) ( | x S T * ( ( )) S V S Picking T from max-entropy distribution implies =O(log n/log log n) suffices.
Technique Properties of Random Spanning Trees [Feder, Mihail] Structure of near min-cuts of a graph.[Karger] Polyhedral : Circulation [Hoffman]
STSP Augmentation problem is matching over odd degree nodes of F
Technique Properties of Random Spanning Trees (Rayleigh Distributions) Structure of near min-cuts of a graph. [Benczur] Polyhedral : Matchings and T-joins [Edmonds, Johnson]
Augmentation Problem Matching over odd degree nodes of F [Edmonds, Edmonds-Johnson] Need to worry about all cuts with odd number of edges in F. Need to worry about near min-cuts of (G,x)
Even Edges and Even Trees An edge e is even for a spanning tree F if all near min-cuts containing e are even. cuts + * ( , s.t. ) F ) 1 ( 2 , ) e S S x (S, S we have that | is )| even (S, S Question: Is there a tree F s.t. the set of even edges is (n).
Structure Theorem Theorem: Let denote the maximum entropy distribution on spanning tree of G s.t. ] [ Pr F F e = * e x ~ Then one of the following holds. 1. (Near Integral) (1- )n edges of fraction 1- . 2. (Many Even Edges) set E* of edges s.t. x*(E*) n and for each e in E* ) s.t. ) , ( cuts [ Pr~ S (S, x S S e F + * 1 ( 2 | , ) even] is )| F (S, S Pr[e is even for F] is constant. Remark: Holds for any fractional solution and not just extreme point solutions.
Christofides** Algorithm 1. If near integral, then select a MST including all near-integral edges deterministically. 2. If many even edges, F be a tree sampled from . 3. Return an Eulerian augmentation of F. Theorem: Christofides** is (3/2- )-approximation for graphical TSP.
Structure of Near Min-cuts Theorem: Structure of near min-cuts of any graph looks very similar to a structure of min-cuts of a graph. Structure of Min-cuts: Cactus Representation [Dinitz, Karzanov, Lomonosov 76] [Fleiner, Frank 08] Structure of near Min-cuts: Polygonal Representation for vertices. [Benczur 96, Benczur-Goemans 08]
Structure Theorem II Theorem: Let x* be any LP solution. Then one of the following holds. 1. (Near Integral) (1- )n edges of fraction 1- . 2. (Good Edges) set E* of edges s.t. x*(E*) n and for each e in E*, the number of near min-cuts containing e is constant.
Structure Theorem Theorem: Let x* be any LP solution. Then one of the following holds. 1. (Near Integral) (1- )n edges of fraction 1- . 2. (Even Edges) set E* of edges s.t. x*(E*) n and for each e in E*, Pr[all near min-cuts containing e are even in F] is a constant.
Good to Even Edges Edge in constant near min-cuts => max entropy tree picks even number of edges in all of the cuts? Expectation: the expected number of edges picked is [2,2+2 ]. Concentration? We need bounds on parity of cuts. Chernoff bounds are not enough.
Better Concentration Log concavity. X be the number of edges in near min-cut C. Pr[X=2]2 >= Pr [X=1]Pr[X=3] Pr[X=2] is a constant. Are we done? Let Y be the number of edges in near min-cut C . Want Pr [X=2 and Y=2] is constant. Pr [X=2 and Y=2] = Pr [X=2] Pr [Y=2|X=2] Let ={ | X=2}. But is not a random spanning measure .
Strongly Rayleigh Measures [Borcea, Branden, Liggett 08] Strongly Rayleigh measures have negative dependence similar to uniform random spanning tree measures. Moreover, they are closed under Projections. Conditioning under certain conditions. Truncation Scaling
Conditioning and Concentration Since is Strongly Rayleigh, ={ |X=2} is also Strongly Rayleigh. Argue Pr [Y=2] is constant. Expectations under may have changed. If an edge is contained in constant number of near min-cuts => the edge is even with constant probability.
Structure Theorem Theorem: Let x* be any LP solution. Then one of the following holds. 1. (Near Integral) (1- )n edges of fraction 1- . 2. (Even Edges) set E* of edges s.t. x*(E*) n and for each e in E*, Pr[all near min-cuts containing e are even in F] is a constant.
Conclusion Symmetric TSP (STSP) Asymmetric TSP (ATSP) log n/log logn approximation [AGGMS 10] 3/2-approximation [Christofides 76] (3/2- )-approximation for graphical TSP [GSS 10] Conjecture: O(1)-approximation 1.461-approximation for graphical TSP [Momke, Svensson 11] Conjecture: 4/3-approximation Conjecture: Christofides* is a (3/2- )-approximation.
