An improved approximation algorithm for the ATSP with parameterized triangle inequality

Keywords

Triangle inequality, Combinatorics, Parameterized complexity, Travelling salesman problem, Mathematics

References

• The probabilistic relationship between the assignment and asymmetric traveling salesman problemsAlan Frieze, Gregory B. Sorkin — 2001
• Network Flows: Theory, Algorithms, and ApplicationsDavid K. Smith, Ravindra K. Ahuja, Thomas L. Magnanti — 1993
• Computers and Intractability: A Guide to the Theory of NP-CompletenessM. R. Garey, David S. Johnson — 1979
• On the relationship between ATSP and the cycle cover problemL. Sunil Chandran, L. Shankar Ram — 2007
• A new approximation algorithm for the asymmetric TSP with triangle inequalityMarkus Bläser — 2003
• A Patching Algorithm for the Nonsymmetric Traveling-Salesman ProblemRichard M. Karp — 1979
• Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphsHaim Kaplan, Moshe Lewenstein, Nira Shafrir — 2003
• THE TRAVELING SALESMAN PROBLEM A Guided Tour of Combinatorial OptimizationNorman Biggs — 1986
• THE TRAVELING SALESMAN PROBLEM : A GUIDED TOUR OF COMBINATORIAL OPTIMIZATIONE. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan — 1985
• Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphsHaim Kaplan, Moshe Lewenstein, Nira Shafrir — 2005
• The probabilistic relationship between the assignment and asymmetric traveling salesman problemsAlan Frieze, Gregory B. Sorkin — 2001
• An Improved Approximation Algorithm for the Asymmetric TSP with Strengthened Triangle InequalityM. Bläser — 2003

Cited by

• Harmonogramowanie przedsięwzięć wieloobiektowych z ciągłą realizacją procesów na działkach roboczychSławomir Biruk, Piotr Jaśkowski — 2010
• The Maximum Hamilton Path Problem with Parameterized Triangle InequalityWeidong Li, Jianping Li, Zefeng Qiao — 2013
• An improved approximation algorithm for the maximum TSPTongquan Zhang, Ying Yin, Jianping Li — 2010
• Deterministic algorithms for multi-criteria Max-TSPBodo Manthey — 2012
• Two Approximation Algorithms for ATSP with Strengthened Triangle InequalityŁukasz Kowalik, Marcin Mucha — 2009
• Deterministic Algorithms for Multi-criteria TSPBodo Manthey, Mitsunori Ogihara, Jun Tarui — 2011
• Minimizing the Duration of Repetitive Construction Processes with Work Continuity ConstraintsPiotr Jaśkowski, Sławomir Biruk — 2019
• From Symmetry to Asymmetry: Generalizing TSP Approximations by ParametrizationLukas Behrendt, Katrin Casel, Tobias Friedrich — 2019
• Approximating the asymmetric p-center problem in parameterized complete digraphsWei Ding, Ke Qiu — 2020

Related papers

• A SOLUTION METHOD FOR THE TRAVELING SALESMAN N PERSON M TOWN PROBLEM (TSP(N/M)) USING THE GENETIC ALGORITHMYutaka Karasawa, Yusa Matsuda, Aiura, Nobunori — 1997
• An Approximation Algorithm for the Maximum Traveling Salesman ProblemA.Yu. Evnin, N.I. Yusova — 2017
• Design of a Decision Support System for Performance Appraisal of Civil Servants with a Fuzzy Multi Attribute Decision Making ModelM. Syahputra — 2020
• On the Relationship between the Biconnectivity Augmentation and Traveling Salesman ProblemsGreg N. Frederickson, Joseph F. JáJá — 1982
• Approximation algorithms for the TSP with sharpened triangle inequalityHans-Joachim Böckenhauer, Juraj Hromkovič, Ralf Klasing — 2000
• On Approximating Multi-Criteria TSPBodo Manthey — 2009