Approximation algorithms with constant factors for a series of asymmetric routing problems

DOI10.1134/s1064562423701454OpenAlexW4392796434MaRDI QIDQ6194441

Mikhail Yu. Khachay, Katherine Neznakhina, K. V. Rizhenko, Yu. Yu. Ogorodnikov

Publication date: 19 March 2024

Published in: Doklady Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1134/s1064562423701454

zbMATH Keywords

approximation algorithmvehicle routing problemasymmetric traveling salesman problemconstant ratioSteiner cycle problemcycle cover problem

Mathematics Subject Classification ID

Mathematical programming (90Cxx) Operations research and management science (90Bxx) Operations research, mathematical programming (90-XX)

Cites Work

• Approximability of the minimum-weight \(k\)-size cycle cover problem
• A note on the prize collecting traveling salesman problem
• The Euclidean traveling salesman problem is NP-complete
• Constant-factor approximations for capacitated arc routing without triangle inequality
• Worst-case analysis of a new heuristic for the travelling salesman problem
• The traveling salesman problem and its variations.
• Constant-factor approximation algorithms for a series of combinatorial routing problems based on the reduction to the asymmetric traveling salesman problem
• Vehicle Routing
• The Design of Approximation Algorithms
• Bounds and Heuristics for Capacitated Routing Problems
• A Constant-factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem
• An O(log n/log log n)-Approximation Algorithm for the Asymmetric Traveling Salesman Problem
• An Improved Approximation Algorithm for The Asymmetric Traveling Salesman Problem
• Handbook of metaheuristics
• FIXED RATIO POLYNOMIAL TIME APPROXIMATION ALGORITHM FOR THE PRIZE-COLLECTING ASYMMETRIC TRAVELING SALESMAN PROBLEM
• Unnamed Item
• Unnamed Item

This page was built for publication: Approximation algorithms with constant factors for a series of asymmetric routing problems