Constant-factor approximation algorithms for a series of combinatorial routing problems based on the reduction to the asymmetric traveling salesman problem

DOI10.1134/S0081543822060128OpenAlexW4321128544MaRDI QIDQ2689288FDOQ2689288

Katherine Neznakhina, M. Yu. Khachaĭ, K. V. Ryzhenko

Publication date: 9 March 2023

Published in: Proceedings of the Steklov Institute of Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

vehicle routing problemprize collecting traveling salesman problemasymmetric traveling salesman problemgeneralized traveling salesman problempolynomial-time reductionconstant-factor approximation algorithmSteiner cycle problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Transportation, logistics and supply chain management (90B06)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• GLNS: an effective large neighborhood search heuristic for the generalized traveling salesman problem
• The prize collecting traveling salesman problem
• Solution of a Large-Scale Traveling-Salesman Problem
• The truck dispatching problem
• The Euclidean traveling salesman problem is NP-complete
• P-Complete Approximation Problems
• A note on the prize collecting traveling salesman problem
• Optimal solutions for routing problems with profits
• Abusing the Tutte Matrix: An Algebraic Instance Compression for the K-set-cycle Problem
• The traveling salesman problem and its variations.
• The time-dependent orienteering problem with time windows: a fast ant colony system
• A quasipolynomial time approximation scheme for Euclidean capacitated vehicle routing
• PTAS FOR k-TOUR COVER PROBLEM ON THE PLANE FOR MODERATELY LARGE VALUES OF k
• The dynamic programming method in the generalized traveling salesman problem
• Improved branch-cut-and-price for capacitated vehicle routing
• An O(log n/log log n)-Approximation Algorithm for the Asymmetric Traveling Salesman Problem
• An improved approximation algorithm for ATSP
• A generic exact solver for vehicle routing and related problems
• A tabu search algorithm for the vehicle routing problem with discrete split deliveries and pickups
• Approximation Algorithms for Generalized MST and TSP in Grid Clusters
• Optimization for drone and drone-truck combined operations: a review of the state of the art and future directions
• Efficient approximation of the metric CVRP in spaces of fixed doubling dimension
• The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme
• VNS methods for home care routing and scheduling problem with temporal dependencies, and multiple structures and specialties
• A constant-factor approximation algorithm for the asymmetric traveling salesman problem
• Budgeted Prize-Collecting Traveling Salesman and Minimum Spanning Tree Problems
• Complexity and approximability of the Euclidean generalized traveling salesman problem in grid clusters
• An exact algorithm with linear complexity for a problem of visiting megalopolises
• Problem-Specific Branch-and-Bound Algorithms for the Precedence Constrained Generalized Traveling Salesman Problem

Cited In (3)

• Approximation algorithms with constant factors for a series of asymmetric routing problems
• Polynomial-time approximability of the asymmetric problem of covering a graph by a bounded number of cycles
• Improved first player strategy for the zero-sum sequential uncrossing game

Uses Software

• VRP
• GTSP-LIB

This page was built for publication: Constant-factor approximation algorithms for a series of combinatorial routing problems based on the reduction to the asymmetric traveling salesman problem

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