On the power of lookahead in on-line server routing problems

DOI10.1016/j.tcs.2008.08.003zbMath1157.68018OpenAlexW2106491296MaRDI QIDQ959800

Luca Allulli, Giorgio Ausiello, Vincenzo Bonifaci, Luigi Laura

Publication date: 12 December 2008

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.08.003

zbMATH Keywords

competitive analysistraveling salesman problemon-line algorithmslookahead

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items (7)

Online machine minimization with lookahead ⋮ On an Online Traveling Repairman Problem with Flowtimes: Worst-Case and Average-Case Analysis ⋮ Time traps in supply chains: is optimal still good enough? ⋮ How much is it worth to know the future in online conversion problems? ⋮ Exact distributional analysis of online algorithms with lookahead ⋮ Online traveling salesman problems with service flexibility ⋮ Online traveling salesman problem with time cost and non-zealous server

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Algorithms for the on-line quota traveling salesman problem
• The on-line asymmetric traveling salesman problem
• An adversarial queueing model for online server routing
• Online algorithms. The state of the art
• A competitive analysis of the list update problem with lookahead
• An improved approximation ratio for the minimum latency problem
• On the influence of lookahead in competitive paging algorithms
• The Online TSP Against Fair Adversaries
• Adversarial queuing theory
• The complexity of the travelling repairman problem
• Beyond Competitive Analysis
• Online k-Server Routing Problems
• Bounds for Certain Multiprocessing Anomalies
• Computing and Combinatorics
• Theory and Applications of Models of Computation
• Algorithms for the on-line travelling salesman
• On-line single-server dial-a-ride problems

This page was built for publication: On the power of lookahead in on-line server routing problems