LP-based solution methods for the asymmetric TSP

DOI10.1016/J.IPL.2006.10.002MaRDI QIDQ845937zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

TSPlinear programmingnetwork flowsapproximation algorithms

Mathematics Subject Classification ID

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

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

Cites work

• scientific article; zbMATH DE number 3898613 (Why is no real title available?)
• scientific article; zbMATH DE number 3904331 (Why is no real title available?)
• scientific article; zbMATH DE number 1305546 (Why is no real title available?)
• A factor 2 approximation algorithm for the generalized Steiner network problem
• Algorithms for a network design problem with crossing supermodular demands
• Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs
• Geometric algorithms and combinatorial optimization
• On the approximability of the traveling salesman problem (extended abstract)
• On the worst-case performance of some algorithms for the asymmetric traveling salesman problem

Cited in

(2)

• A Simple LP Relaxation for the Asymmetric Traveling Salesman Problem
• A Lagrangian Based Approach for the Asymmetric Generalized 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)