An asymptotically tight online algorithm for \(m\)-steiner traveling salesman problem

DOI10.1016/j.ipl.2021.106177OpenAlexW3194414553MaRDI QIDQ2059872

Qirong Chen, Yubai Zhang, Zhao Zhang, Zhaohui Liu

Publication date: 14 December 2021

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2021.106177

zbMATH Keywords

analysis of algorithmson-line algorithmsSteiner traveling salesman problemblockages

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Compact formulations of the Steiner traveling salesman problem and related problems
• The Steiner traveling salesman problem with online edge blockages
• Improved approximation algorithms for some min-max and minimum cycle cover problems
• An analysis of the extended Christofides heuristic for the \(k\)-depot TSP
• A cutting plane procedure for the travelling salesman problem on road networks
• The traveling salesman problem: An overview of exact and approximate algorithms
• The traveling salesman problem and its variations
• The Steiner traveling salesman problem with online advanced edge blockages
• An extension of the Christofides heuristic for the generalized multiple depot multiple traveling salesmen problem
• The \(m\)-Steiner traveling salesman problem with online edge blockages
• The covering Canadian traveller problem
• An approximation algorithm for a symmetric generalized multiple depot, multiple travelling salesman problem
• Approximation Algorithms for Min-Max Cycle Cover Problems
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• The Multiobjective Traveling Salesman Problem: A Survey and a New Approach
• The traveling salesman problem on a graph and some related integer polyhedra
• A GRASP heuristic using path‐relinking and restarts for the Steiner traveling salesman problem
• Bounds for Certain Multiprocessing Anomalies
• New approximation algorithms for the minimum cycle cover problem
• A cutting plane algorithm for the general routing problem
• A note on computational aspects of the Steiner traveling salesman problem

This page was built for publication: An asymptotically tight online algorithm for \(m\)-steiner traveling salesman problem