On the relationship between ATSP and the cycle cover problem

DOI10.1016/J.TCS.2006.10.026MaRDI QIDQ868952zbMATH OpenOpenAlexFDO

Authors 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 optimizationassignment problemapproximation algorithmstraveling salesman problemcycle 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)

Recommendations

• scientific article; zbMATH DE number 2086388
• An improved approximation algorithm for the ATSP with parameterized triangle inequality
• Two Approximation Algorithms for ATSP with Strengthened Triangle Inequality
• scientific article; zbMATH DE number 2038707
• An improved approximation algorithm for the asymmetric TSP with strengthened triangle inequality

Cites work

• scientific article; zbMATH DE number 3908167 (Why is no real title available?)
• scientific article; zbMATH DE number 3932819 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2038707 (Why is no real title available?)
• scientific article; zbMATH DE number 3409134 (Why is no real title available?)
• A Patching Algorithm for the Nonsymmetric Traveling-Salesman Problem
• An improved approximation algorithm for the asymmetric TSP with strengthened triangle inequality
• Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs
• Approximation algorithms for the TSP with sharpened triangle inequality
• On patching algorithms for random asymmetric travelling salesman problems
• On the traveling salesman problem restricted to inputs satisfying a relaxed triangle inequality
• On the worst-case performance of some algorithms for the asymmetric traveling salesman problem
• Performance Guarantees for Approximation Algorithms Depending on Parametrized Triangle Inequalities
• Performance guarantees for the TSP with a parameterized triangle inequality
• STACS 2004
• The probabilistic relationship between the assignment and asymmetric traveling salesman problems.
• Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman problem.
• When Is the Assignment Bound Tight for the Asymmetric Traveling-Salesman Problem?

Cited in

(12)

• An overview of graph covering and partitioning
• Two Approximation Algorithms for ATSP with Strengthened Triangle Inequality
• Approximating the asymmetric \(p\)-center problem in parameterized complete digraphs
• scientific article; zbMATH DE number 2086388 (Why is no real title available?)
• Deterministic algorithms for multi-criteria TSP
• Improved approximation algorithms for metric maximum ATSP and maximum 3-cycle cover problems
• Minimum-Weight Cycle Covers and Their Approximability
• An improved approximation algorithm for the maximum TSP
• Approximability of the minimum-weight \(k\)-size cycle cover problem
• Methods for solving fuzzy assignment problems and fuzzy travelling salesman problems with different membership functions
• Minimum-weight cycle covers and their approximability
• Greedy cycles in the star graphs

This page was built for publication: On the relationship between ATSP and the cycle cover problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q868952)