کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4952185 | 1442019 | 2017 | 12 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Infinite linear programming and online searching with turn cost
ترجمه فارسی عنوان
برنامه نویسی بی نهایت خطی و جستجو آنلاین با هزینه نوبت
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
مشکلات جستجو و اکتشاف برنامه نویسی بی نهایت، تجزیه و تحلیل رقابتی الگوریتم های آنلاین،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We consider the problem of searching for a hidden target in an environment that consists of a set of concurrent rays. Every time the searcher turns direction, it incurs a fixed cost. The objective is to derive a search strategy for locating the target as efficiently as possible, and the performance of the strategy is evaluated by means of the well-established competitive ratio. In this paper we revisit an approach due to Demaine et al. [8] based on infinite linear-programming formulations of this problem. We first demonstrate that their definition of duality in infinite LPs can lead to erroneous results. We then provide a non-trivial correction which establishes the optimality of a certain round-robin search strategy.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 670, 29 March 2017, Pages 11-22
Journal: Theoretical Computer Science - Volume 670, 29 March 2017, Pages 11-22
نویسندگان
Spyros Angelopoulos, Diogo Arsénio, Christoph Dürr,