کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10331909 | 686963 | 2015 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Approximation algorithms for the arc orienteering problem
ترجمه فارسی عنوان
الگوریتم تقریبی برای مسئله جهت گیری قوس
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
In this article we present approximation algorithms for the Arc Orienteering Problem (AOP). We propose a polylogarithmic approximation algorithm in directed graphs, while in undirected graphs we give a (6+ϵ+o(1)) and a (4+ϵ)-approximation algorithm for arbitrary instances and instances of unit profit, respectively. Also, an inapproximability result for the AOP is obtained as well as approximation algorithms for the Mixed Orienteering Problem.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 115, Issue 2, February 2015, Pages 313-315
Journal: Information Processing Letters - Volume 115, Issue 2, February 2015, Pages 313-315
نویسندگان
Damianos Gavalas, Charalampos Konstantopoulos, Konstantinos Mastakas, Grammati Pantziou, Nikolaos Vathis,