کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
428468 686667 2006 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
BubbleSearch: A simple heuristic for improving priority-based greedy algorithms
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
BubbleSearch: A simple heuristic for improving priority-based greedy algorithms
چکیده انگلیسی

We introduce BubbleSearch, a general approach for extending priority-based greedy heuristics. Following the framework recently developed by Borodin et al., we consider priority algorithms, which sequentially assign values to elements in some fixed or adaptively determined order. BubbleSearch extends priority algorithms by selectively considering additional orders near an initial good ordering. While many notions of nearness are possible, we explore algorithms based on the Kendall-tau distance (also known as the BubbleSort distance) between permutations. Our contribution is to elucidate the BubbleSearch paradigm and experimentally demonstrate its effectiveness.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 97, Issue 4, 28 February 2006, Pages 161-169