An Improved Online Algorithm for the Traveling Repairperson Problem on a Line

DOI10.4230/LIPIcs.MFCS.2019.6OpenAlexW2970958781MaRDI QIDQ5092364

Hsiang-Hsuan Liu, Marcin Bienkowski

Publication date: 21 July 2022

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2019/10950/pdf/LIPIcs-MFCS-2019-6.pdf/

zbMATH Keywords

competitive analysisfactor-revealing LPminimizing completion timetraveling repairperson problem

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (6)

Efficient algorithms for ride-hitching in UAV travelling ⋮ Tight analysis of the lazy algorithm for open online dial-a-ride ⋮ An improved algorithm for open online dial-a-ride ⋮ Online ride-hitching in UAV travelling ⋮ Improved bounds for open online dial-a-ride on the line ⋮ Weighted online minimum latency problem with edge uncertainty

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Searching in the plane
• Online \(k\)-server routing problems
• A hard dial-a-ride problem that is easy on average
• New lower bounds for online \(k\)-server routing problems
• An improved approximation ratio for the minimum latency problem
• News from the online traveling repairman.
• Tight Analysis of the Smartstart Algorithm for Online Dial-a-Ride on the Line
• The complexity of the travelling repairman problem
• Tight Bounds for Online TSP on the Line
• Serving requests with on-line routing
• Competitive algorithms for the on-line traveling salesman
• Polynomial time approximation schemes for the traveling repairman and other minimum latency problems.
• Approximation and Online Algorithms
• Algorithms for the on-line travelling salesman
• On-line single-server dial-a-ride problems

This page was built for publication: An Improved Online Algorithm for the Traveling Repairperson Problem on a Line