The online prize-collecting traveling salesman problem

DOI10.1016/j.ipl.2008.03.002zbMath1190.90152OpenAlexW2151159917MaRDI QIDQ963439

Giorgio Ausiello, Luigi Laura, Vincenzo Bonifaci

Publication date: 19 April 2010

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

Full work available at URL: http://hdl.handle.net/11590/379873

zbMATH Keywords

combinatorial problemsanalysis of algorithmson-line algorithms

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27)

Related Items (10)

Optimal deterministic algorithms for some variants of online quota traveling salesman problem ⋮ The Canadian tour operator problem on paths: tight bounds and resource augmentation ⋮ The Post-Disaster Debris Clearance Problem Under Incomplete Information ⋮ From theory to practice: maximizing revenues for on-line dial-a-ride ⋮ Car-sharing between two locations: online scheduling with flexible advance bookings ⋮ Online traveling salesman problem with deadlines and service flexibility ⋮ Improved bounds for revenue maximization in time-limited online dial-a-ride ⋮ The online prize-collecting traveling salesman problem ⋮ 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
• Algorithms for the on-line quota traveling salesman problem
• The online prize-collecting traveling salesman problem
• Saving an epsilon
• The prize collecting traveling salesman problem
• New Approximation Guarantees for Minimum-Weight k-Trees and Prize-Collecting Salesmen
• A General Approximation Technique for Constrained Forest Problems
• On Prize‐collecting Tours and the Asymmetric Travelling Salesman Problem
• Algorithms for the on-line travelling salesman

This page was built for publication: The online prize-collecting traveling salesman problem