Approximating minimum-cost connected \(T\)-joins
From MaRDI portal
Publication:2345942
DOI10.1007/s00453-013-9850-8zbMath1322.68264arXiv1207.5722OpenAlexW1965608008MaRDI QIDQ2345942
Zhihan Gao, Zachary Friggstad, Joseph Cheriyan
Publication date: 21 May 2015
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1207.5722
primal-dual methodtraveling salesman problemapproximation algorithmsLP rounding\(T\)-joinsprize-collecting problems\(s, t\)-path TSP
Related Items (7)
Improving on best-of-many-Christofides for \(T\)-tours ⋮ Constant-factor approximation algorithms for parity-constrained facility location and \(k\)-center ⋮ Minimum $T$-Joins and Signed-Circuit Covering ⋮ Unnamed Item ⋮ Reassembling Trees for the Traveling Salesman ⋮ Better \(s-t\)-tours by Gao trees ⋮ Reducing Path TSP to TSP
Cites Work
- Unnamed Item
- Unnamed Item
- Shorter tours by nicer ears: \(7/5\)-approximation for the graph-TSP, \(3/2\) for the path version, and \(4/3\) for two-edge-connected subgraphs
- A construction for binary matroids
- Analysis of Christofides' heuristic: some paths are more difficult than cycles
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Approximate \(k\)-MSTs and \(k\)-Steiner trees via the primal-dual method and Lagrangean relaxation
- Worst-case analysis of a new heuristic for the travelling salesman problem
- The Design of Approximation Algorithms
- Improved Approximation Algorithms for Prize-Collecting Steiner Tree and TSP
- Iterative Methods in Combinatorial Optimization
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- The prize collecting traveling salesman problem
- A General Approximation Technique for Constrained Forest Problems
- Eight-Fifth Approximation for the Path TSP
- Improving christofides' algorithm for the s-t path TSP
- A Randomized Rounding Approach to the Traveling Salesman Problem
- Approximating Graphic TSP by Matchings
This page was built for publication: Approximating minimum-cost connected \(T\)-joins
