Deterministic algorithms for multi-criteria max-TSP

DOI10.1016/j.dam.2012.05.007zbMath1278.90361OpenAlexW2094749368MaRDI QIDQ713324

Bodo Manthey

Publication date: 26 October 2012

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2012.05.007

zbMATH Keywords

traveling salesman problemapproximation algorithmsmulticriteria optimizationPareto curves

Mathematics Subject Classification ID

Multi-objective and goal programming (90C29) Combinatorial optimization (90C27)

Related Items

Approximation Methods for Multiobjective Optimization Problems: A Survey ⋮ Bi-objective matchings with the triangle inequality

Cites Work

• Unnamed Item
• Unnamed Item
• Multi-criteria TSP: Min and Max combined
• Approximation algorithms for multi-criteria traveling salesman problems
• Matching is as easy as matrix inversion
• Approximating maximum weight cycle covers in directed graphs with weights zero and one
• Applications of Discrepancy Theory in Multiobjective Approximation
• On approximating multicriteria TSP
• Approximating Multi-criteria Max-TSP
• Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size
• Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs
• Approximability and Hardness in Multi-objective Optimization
• Improved Approximation Ratios for Traveling Salesperson Tours and Paths in Directed Graphs
• A 7/9 - Approximation Algorithm for the Maximum Traveling Salesman Problem
• The complexity of restricted spanning tree problems
• Multicriteria Optimization
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques