تقرير
Multi Purpose Routing: New Perspectives and Approximation Algorithms
| العنوان: | Multi Purpose Routing: New Perspectives and Approximation Algorithms |
|---|---|
| المؤلفون: | Farhadi, Majid, Moondra, Jai, Tetali, Prasad, Toriello, Alejandro |
| سنة النشر: | 2022 |
| المجموعة: | Computer Science |
| مصطلحات موضوعية: | Computer Science - Data Structures and Algorithms, 68W25 (Primary) 68Q25, 90C27 (Secondary), F.2.2 |
| الوصف: | The cost due to delay in services may be intrinsically different for various applications of vehicle routing such as medical emergencies, logistical operations, and ride-sharing. We study a fundamental generalization of the Traveling Salesman Problem, namely $L_p$ TSP, where the objective is to minimize an aggregated measure of the delay in services, quantified by the Minkowski $p$-norm of the delay vector. We present efficient combinatorial and Linear Programming algorithms for approximating $L_p$ TSP on general metrics. We provide several approximation algorithms for the $L_p$ TSP problem, including $4.27$ & $10.92$-approximation algorithms for single & multi vehicle $L_2$ TSP, called the Traveling Firefighter Problem. Among other contributions, we provide an $8$-approximation and a $1.78$ inapproximability for All-Norm TSP problem, addressing scenarios where one does not know the ideal cost function, or is seeking simultaneous approximation with respect to any cost function. Comment: arXiv admin note: substantial text overlap with arXiv:2107.10454 |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2208.04410 |
| رقم الأكسشن: | edsarx.2208.04410 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |