On the relationship between ATSP and the cycle cover problem

DOI10.1016/j.tcs.2006.10.026zbMath1113.90161OpenAlexW2019570365MaRDI QIDQ868952

L. Sunil Chandran, L. Shankar Ram

Publication date: 26 February 2007

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2006.10.026

zbMATH Keywords

combinatorial optimizationtraveling salesman problemassignment problemapproximation algorithmscycle cover

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items

An overview of graph covering and partitioning, Two Approximation Algorithms for ATSP with Strengthened Triangle Inequality, Approximability of the minimum-weight \(k\)-size cycle cover problem, Greedy cycles in the star graphs, Approximating the asymmetric \(p\)-center problem in parameterized complete digraphs, Methods for solving fuzzy assignment problems and fuzzy travelling salesman problems with different membership functions, Minimum-Weight Cycle Covers and Their Approximability, Deterministic Algorithms for Multi-criteria TSP, An improved approximation algorithm for the maximum TSP, Approximation algorithms for multi-criteria traveling salesman problems, Minimum-weight cycle covers and their approximability

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Performance guarantees for the TSP with a parameterized triangle inequality
• Approximation algorithms for the TSP with sharpened triangle inequality
• An improved approximation algorithm for the asymmetric TSP with strengthened triangle inequality
• Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman problem.
• On patching algorithms for random asymmetric travelling salesman problems
• On the traveling salesman problem restricted to inputs satisfying a relaxed triangle inequality
• Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs
• A Patching Algorithm for the Nonsymmetric Traveling-Salesman Problem
• On the worst-case performance of some algorithms for the asymmetric traveling salesman problem
• Performance Guarantees for Approximation Algorithms Depending on Parametrized Triangle Inequalities
• When Is the Assignment Bound Tight for the Asymmetric Traveling-Salesman Problem?
• STACS 2004