2009/07/30 by Greg N. Frederickson, Frederickson, Greg N., Barry Wittman +1
Computer Science · #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #cs.DS
paper · pdf · doi:10.48550/arxiv.0907.5372
16 pages, 3 figures
arxiv created 2009/07/30 · arxiv updated 2009/12/01
The input to the unrooted traveling repairman problem is an undirected metric graph and a subset of nodes, each of which has a time window of unit length. Given that a repairman can start at any location, the goal is to plan a route that visits as many nodes as possible during their respective time windows. A polynomial-time bicriteria approximation algorithm is presented for this problem, gaining an increased fraction of repairman visits for increased speedup of repairman motion. For speedup s, we find a 6γ/(s + 1)-approximation for s in the range 1 ≤ s ≤ 2 and a 4γ/s-approximation for s in the range 2 ≤ s ≤ 4, where γ= 1 on tree-shaped networks and γ= 2 + ε on general metric graphs.