Approximation algorithms for multi-criteria traveling salesman problems

DOI10.1007/s00453-007-9011-zzbMath1161.90019arXivcs/0606040OpenAlexW1902458947MaRDI QIDQ1017906

Bodo Manthey, L. Shankar Ram

Publication date: 13 May 2009

Published in: Algorithmica, Approximation and Online Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/cs/0606040

zbMATH Keywords

traveling salesman problemapproximation algorithmsmulti-criteria optimization

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Multi-objective and goal programming (90C29) Approximation methods and heuristics in mathematical programming (90C59) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items

Generation of the exact Pareto set in multi-objective traveling salesman and set covering problems, Advancing local search approximations for multiobjective combinatorial optimization problems, Novel concave hull-based heuristic algorithm for TSP, Approximation Methods for Multiobjective Optimization Problems: A Survey, Multi-criteria TSP: Min and Max combined, Approximating Multi-criteria Max-TSP, Deterministic Algorithms for Multi-criteria TSP, Deterministic algorithms for multi-criteria max-TSP

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An improved approximation algorithm for the asymmetric TSP with strengthened triangle inequality
• On the relationship between ATSP and the cycle cover problem
• Matching theory
• Exact arborescences, matchings and cycles
• Matching is as easy as matrix inversion
• The traveling salesman problem and its variations
• A survey and annotated bibliography of multiobjective combinatorial optimization
• Approximating the Pareto curve with local search for the bicriteria TSP(1,2) problem
• Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs
• 8/7-approximation algorithm for (1,2)-TSP
• The complexity of restricted spanning tree problems
• An Analysis of Several Heuristics for the Traveling Salesman Problem
• Multicriteria Optimization
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Fundamentals of Computation Theory
• A Short Proof of the Factor Theorem for Finite Graphs