کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
8960191 | 1646386 | 2018 | 22 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Taxi-sharing: Parameterized complexity and approximability of the dial-a-ride problem with money as an incentive
ترجمه فارسی عنوان
به اشتراک گذاری تاکسی: پیچیدگی پارامتریکی و تقریب زنی مشکل شماره گیری سوار با پول به عنوان یک انگیزه
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
پیچیدگی پارامتریک، تقریب پذیری، مشکل شماره گیری سوار، به اشتراک گذاری تاکسی،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Among other results, we prove that 1-DARP-M is NP-Complete and max-DARP-M and max-1-DARP-M cannot be approximated in polynomial time to within any variable ratio even if α, capa and TW are fixed and if the road network is a planar graph. We also give a polynomial algorithm for max-1-DARP-M for the case where capa and TW are fixed and where the network does not contain a circuit. This algorithm implies a 1n-polynomial approximation for max-DARP-M.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 745, 12 October 2018, Pages 202-223
Journal: Theoretical Computer Science - Volume 745, 12 October 2018, Pages 202-223
نویسندگان
Dimitri Watel, Alain Faye,