An approximation algorithm for the asymmetric travelling salesman problem with distances one and two

DOI10.1016/0020-0190(92)90103-3zbMath0795.68101OpenAlexW2021625223MaRDI QIDQ1209363

Sundar Vishwanathan

Publication date: 16 May 1993

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(92)90103-3

zbMATH Keywords

combinatorial optimizationapproximation algorithmasymmetric travelling salesman problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Deterministic network models in operations research (90B10)

Related Items (13)

Differential approximation results for the traveling salesman and related problems ⋮ When the greedy algorithm fails ⋮ Lower and upper competitive bounds for online directed graph exploration ⋮ Sequentially Swapping Colored Tokens on Graphs ⋮ A worst-case analysis of two approximate algorithms for the asymmetric travelling salesman problem ⋮ Approximating the directed path partition problem ⋮ New Approximation Algorithms for (1,2)-TSP ⋮ The path partition problem and related problems in bipartite graphs ⋮ Maximum ATSP with weights zero and one via half-edges ⋮ Improved integrality gap upper bounds for traveling salesperson problems with distances one and two ⋮ An approximation algorithm for the minimum co-path set problem ⋮ Nontrivial path covers of graphs: existence, minimization and maximization ⋮ (1,2)-HAMILTONIAN COMPLETION ON A MATCHING

Cites Work

• On mapping processes to processors in distributed systems
• Optimal covering of cacti by vertex-disjoint paths
• Approximation algorithms for covering a graph by vertex-disjoint paths of maximum total weight
• A Patching Algorithm for the Nonsymmetric Traveling-Salesman Problem
• On the worst-case performance of some algorithms for the asymmetric traveling salesman problem
• Covering Points of a Digraph with Point-Disjoint Paths and Its Application to Code Optimization
• An Analysis of Several Heuristics for the Traveling Salesman Problem
• The Traveling Salesman Problem with Distances One and Two
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: An approximation algorithm for the asymmetric travelling salesman problem with distances one and two