کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4951236 | 1441198 | 2017 | 19 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Combinatorial filter reduction: Special cases, approximation, and fixed-parameter tractability
ترجمه فارسی عنوان
کاهش فیلتر ترکیبی: موارد خاص، تقریبی، و پایایی ثابت پارامتر
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
فیلترهای ترکیبی کاهش، خودکار نزدیک شدن پارامتر ثابت،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Recent research in algorithmic robotics considers combinatorial filters, which concisely capture the discrete structure underlying many reasoning problems for robots. An important recent result is that the filter minimization problem-Given a filter, find the smallest equivalent filter-is NP-hard. This paper extends that result along several dimensions, including hardness proofs for some natural special cases and for approximation, and new results analyzing the only known algorithm for this problem. We show that this problem is not fixed-parameter tractable for any of the obvious parameters, but it is fixed-parameter tractable for a certain combination of new parameters.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computer and System Sciences - Volume 85, May 2017, Pages 74-92
Journal: Journal of Computer and System Sciences - Volume 85, May 2017, Pages 74-92
نویسندگان
Fatemeh Zahra Saberifar, Ali Mohades, Mohammadreza Razzazi, Jason M. O'Kane,