LP-based solution methods for the asymmetric TSP

DOI10.1016/J.IPL.2006.10.002zbMATH Open1184.68645OpenAlexW1989453147MaRDI QIDQ845937FDOQ845937

Authors: Vardges Melkonian 

Publication date: 29 January 2010

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

Full work available at URL: https://doi.org/10.1016/j.ipl.2006.10.002

Recommendations

• A Simple LP Relaxation for the Asymmetric Traveling Salesman Problem
• A simple LP relaxation for the asymmetric traveling salesman problem
• scientific article; zbMATH DE number 1445294
• A Constant-factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem

zbMATH Keywords

TSPlinear programmingnetwork flowsapproximation algorithms

Mathematics Subject Classification ID

Linear programming (90C05) Approximation algorithms (68W25)

Cites Work

• Geometric algorithms and combinatorial optimization
• On the worst-case performance of some algorithms for the asymmetric traveling salesman problem
• Title not available (Why is that?)
• On the approximability of the traveling salesman problem (extended abstract)
• Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs
• A factor 2 approximation algorithm for the generalized Steiner network problem
• Title not available (Why is that?)
• Title not available (Why is that?)
• Algorithms for a network design problem with crossing supermodular demands

Cited In (2)

• A Lagrangian Based Approach for the Asymmetric Generalized Traveling Salesman Problem
• A Simple LP Relaxation for the Asymmetric Traveling Salesman Problem

This page was built for publication: LP-based solution methods for the asymmetric TSP

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