کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419838 | 683866 | 2008 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Semi-preemptive routing on trees
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Semi-preemptive routing on trees Semi-preemptive routing on trees](/preview/png/419838.png)
چکیده انگلیسی
We study a variant of the pickup-and-delivery problem (PDP) in which the objects that have to be transported can be reloaded at most dd times, for a given d∈Nd∈N. This problem is known to be polynomially solvable on paths or cycles and NP-complete on trees. We present a (4/3+ε)(4/3+ε)-approximation algorithm if the underlying graph is a tree. By using a result of Charikar et al. [M. Charikar, C. Chekuri, A. Goel, S. Guha, S. Plotkin, Approximating a finite metric by a small number of tree metrics, in: FOCS ’98: Proceedings of the 39th Annual Symposium on Foundations of Computer Science, IEEE Computer Society, Washington, DC, USA, 1998, pp. 379–388], this can be extended to a O(lognloglogn)O(lognloglogn)-approximation for general graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 156, Issue 17, 28 October 2008, Pages 3298–3304
Journal: Discrete Applied Mathematics - Volume 156, Issue 17, 28 October 2008, Pages 3298–3304
نویسندگان
Sven O. Krumke, Dirk Räbiger, Rainer Schrader,