Loading...
Please wait, while we are loading the content...
Similar Documents
The k-Traveling Repairman Problem (2003)
| Content Provider | CiteSeerX |
|---|---|
| Author | Fakcharoenphol, Jittat Harrelson, Chris Rao, Satish |
| Description | We consider the k-traveling repairman problem, a generalization of the metric traveling repairman problem, also known as the minimum latency problem, to multiple repairmen. We give an 8.497#-approximation algorithm for this generalization, where # denotes the best achievable approximation factor for the problem of finding the least cost rooted tree spanning i vertices (i-MST) problem. This can be compared with the best known approximation algorithm for the case k = 1, which is 3.59#. We are aware of no previous work on the approximability of the present problem. |
| File Format | |
| Language | English |
| Publisher Date | 2003-01-01 |
| Publisher Institution | Proceedings of the 14th annual ACM-SIAM symposium on Discrete algorithms |
| Access Restriction | Open |
| Subject Keyword | Present Problem Repairman Problem Previous Work K-traveling Repairman Problem Achievable Approximation Factor Approximation Algorithm Known Approximation Algorithm Minimum Latency Problem |
| Content Type | Text |
| Resource Type | Article |
