کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
476766 | 1446055 | 2013 | 9 صفحه PDF | دانلود رایگان |
Given k identical salesmen, where k ⩾ 2 is a constant independent of the input size, the min–max k-traveling salesmen problem on a tree is to determine a set of k tours for the salesmen to serve all customers that are located on a tree-shaped network, so that each tour starts from and returns to the root of the tree with the maximum total edge weight of the tours minimized. The problem is known to be NP-hard even when k = 2. In this paper, we have developed a pseudo-polynomial time exact algorithm for this problem with any constant k ⩾ 2, closing a question that has remained open for a decade. Along with this, we have further developed a (1 + ϵ)-approximation algorithm for any ϵ > 0.
► Studied the min–max k-traveling salesman problem on a tree (k-TSPT).
► Developed the first pseudo-polynomial time exact algorithm for the min–max k-TSPT.
► Closed an open question related to the min–max k-TSPT.
► Developed the first (1 + ε)-approximation algorithm for the min–max k-TSPT.
Journal: European Journal of Operational Research - Volume 227, Issue 2, 1 June 2013, Pages 284–292