8/7-approximation algorithm for (1,2)-TSP

DOI10.1145/1109557.1109627zbMath1192.90158OpenAlexW268194639WikidataQ55899756 ScholiaQ55899756MaRDI QIDQ3581504

Piotr Berman, Marek Karpinski

Publication date: 16 August 2010

Published in: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1109557.1109627

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (34)

Traveling salesman problems in temporal graphs ⋮ On residual approximation in solution extension problems ⋮ Constant Factor Approximation for ATSP with Two Edge Weights ⋮ Method of scaling in approximate solution of the traveling salesman problem ⋮ Approximation hardness of graphic TSP on cubic graphs ⋮ A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem ⋮ Cubic TSP: A 1.3-Approximation ⋮ Discrete heat transfer search for solving travelling salesman problem ⋮ On global integer extrema of real-valued box-constrained multivariate quadratic functions ⋮ Towards Better Inapproximability Bounds for TSP: A Challenge of Global Dependencies ⋮ Approximations for the Steiner multicycle problem ⋮ Geometric Network Creation Games ⋮ Approximating the directed path partition problem ⋮ Network Reconstruction – A New Approach to the Traveling Salesman Problem and Complexity ⋮ Isomorphic coupled-task scheduling problem with compatibility constraints on a single processor ⋮ The traveling salesman problem on cubic and subcubic graphs ⋮ Approximation results for the weighted \(P_4\) partition problem ⋮ New Approximation Algorithms for (1,2)-TSP ⋮ New inapproximability bounds for TSP ⋮ Time complexity analysis of evolutionary algorithms for 2-hop \((1,2)\)-minimum spanning tree problem ⋮ TSP on Cubic and Subcubic Graphs ⋮ Deterministic Algorithms for Multi-criteria TSP ⋮ Improved integrality gap upper bounds for traveling salesperson problems with distances one and two ⋮ An approximation algorithm for the minimum co-path set problem ⋮ Unnamed Item ⋮ TSP with bounded metrics ⋮ A minimum spanning tree based heuristic for the travelling salesman tour ⋮ Approximation of the double traveling salesman problem with multiple stacks ⋮ Characterizing the Integrality Gap of the Subtour LP for the Circulant Traveling Salesman Problem ⋮ Constant factor approximation for ATSP with two edge weights ⋮ Approximation algorithms for multi-criteria traveling salesman problems ⋮ On the approximation ratio of the 3-opt algorithm for the \((1,2)\)-TSP ⋮ Approximation algorithms for the 2-peripatetic salesman problem with edge weights 1 and 2 ⋮ An approximation algorithm for a bottleneck traveling salesman problem

This page was built for publication: 8/7-approximation algorithm for (1,2)-TSP