Optimal deterministic algorithms for some variants of online quota traveling salesman problem

DOI10.1016/j.ejor.2014.04.037zbMath1338.90359OpenAlexW2103307401MaRDI QIDQ296870

Wei Yu, Zhaohui Liu, Xiaoguang Bao

Publication date: 23 June 2016

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2014.04.037

zbMATH Keywords

traveling salesmancompetitive ratioonline algorithmquota TSP

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)

Related Items

A simulated annealing algorithm for the restricted stochastic traveling salesman problem with exponentially distributed arc lengths, Online traveling salesman problem with time cost and non-zealous server

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The orienteering problem: a survey
• Algorithms for the on-line quota traveling salesman problem
• The on-line asymmetric traveling salesman problem
• The online prize-collecting traveling salesman problem
• An adversarial queueing model for online server routing
• Online algorithms. The state of the art
• The Online TSP Against Fair Adversaries
• New Approximation Guarantees for Minimum-Weight k-Trees and Prize-Collecting Salesmen
• Algorithms for the on-line travelling salesman