Computer Science – Data Structures and Algorithms
Scientific paper
2009-07-30
Computer Science
Data Structures and Algorithms
16 pages, 3 figures
Scientific paper
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\gamma/(s + 1)$-approximation for $s$ in the range $1 \leq s \leq 2$ and a $4\gamma/s$-approximation for $s$ in the range $2 \leq s \leq 4$, where $\gamma = 1$ on tree-shaped networks and $\gamma = 2 + \epsilon$ on general metric graphs.
Frederickson Greg N.
Wittman Barry
No associations
LandOfFree
Speedup in the Traveling Repairman Problem with Unit Time Windows does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Speedup in the Traveling Repairman Problem with Unit Time Windows, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Speedup in the Traveling Repairman Problem with Unit Time Windows will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-469307