An improved approximation algorithm for the traveling salesman problem with relaxed triangle inequality
From MaRDI portal
Publication:2353642
Abstract: Given a complete edge-weighted graph G, we present a polynomial time algorithm to compute a degree-four-bounded spanning Eulerian subgraph of 2G that has at most 1.5 times the weight of an optimal TSP solution of G. Based on this algorithm and a novel use of orientations in graphs, we obtain a (3 beta/4 + 3 beta^2/4)-approximation algorithm for TSP with beta-relaxed triangle inequality (beta-TSP), where beta >= 1. A graph G is an instance of beta-TSP, if it is a complete graph with non-negative edge weights that are restricted as follows. For each triple of vertices u,v,w in V(G), c({u,v}) <= beta (c({u,w}) + c({w,v})).
Recommendations
- Approximation algorithms for the TSP with sharpened triangle inequality
- On the traveling salesman problem restricted to inputs satisfying a relaxed triangle inequality
- Improved approximations for ordered TSP on near-metric graphs (extended abstract)
- scientific article; zbMATH DE number 1500530
- Two Approximation Algorithms for ATSP with Strengthened Triangle Inequality
Cites work
- \(\frac{13}{9}\)-approximation for graphic TSP
- A Randomized Rounding Approach to the Traveling Salesman Problem
- Approximating Graphic TSP by Matchings
- Approximating minimum bounded degree spanning trees to within one of optimal
- Approximation algorithms for multi-dimensional assignment problems with decomposable costs
- Degree bounded matroids and submodular flows
- scientific article; zbMATH DE number 3862930 (Why is no real title available?)
- Matching, Euler tours and the Chinese postman
- On the traveling salesman problem restricted to inputs satisfying a relaxed triangle inequality
- Performance Guarantees for Approximation Algorithms Depending on Parametrized Triangle Inequalities
- Performance guarantees for the TSP with a parameterized triangle inequality
- 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
- The Traveling-Salesman Problem and Minimum Spanning Trees
- Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman problem.
Cited in
(14)- Approximability and inapproximability of the star p-hub center problem with parameterized triangle inequality
- A 4-approximation algorithm for the TSP-path satisfying a biased triangle inequality
- On the approximability of the single allocation \(p\)-hub center problem with parameterized triangle inequality
- Approximation algorithms for the \(p\)-hub center routing problem in parameterized metric graphs
- On the traveling salesman problem restricted to inputs satisfying a relaxed triangle inequality
- Improved approximations for ordered TSP on near-metric graphs (extended abstract)
- Performance guarantees for the TSP with a parameterized triangle inequality
- Approximation algorithms for the TSP with sharpened triangle inequality
- Constant factor approximation algorithm for TSP satisfying a biased triangle inequality
- Improved approximations for ordered TSP on near-metric graphs
- A Modern View on Stability of Approximation
- On a traveling salesman problem for points in the unit cube
- On the hardness and approximation of the densest k-subgraph problem in parameterized metric graphs
- An FPT factor-11 approximation algorithm for TSP
This page was built for publication: An improved approximation algorithm for the traveling salesman problem with relaxed triangle inequality
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2353642)
