BubbleSearch: Generic Methods for Improving Greedy Algorithms
We have developed generic methods for extending a popular class of greedy algorithms called priority algorithms. Our techniques produce anytime algorithms that can find better solutions than the original priority algorithm, given more computation time. Our techniques modify the order in which the priority algorithm considers the problem elements based on the Kendall-tau distance between orderings. The Kendall-tau distance is also known as the BubbleSort distance, which is why we call our approach BubbleSearch. We present both exhaustive and randomized variations of BubbleSearch. Our experiments in four domains show that even 100 iterations of BubbleSearch substantially improves the result compared to the original priority algorithm.
Background & Objective: Priority algorithms have historically been used and are especially effective at solving many scheduling and packing problems. They are attractive because they are simple to design and implement, execute quickly, and often provide very good heuristic solutions. For some problems, they are the best-known heuristic. We have developed generic algorithms and software, which can extend any priority algorithm that, fits our formulation. Our approach is essentially an easy way to augment a good priority algorithm to make it better.
Technical Discussion: Priority algorithms consist of an ordering function and a placement function. A priority algorithm sequentially assigns values to elements according to the ordering of elements using its placement function. For example, the First Fit Decreasing algorithm for bin packing sequentially places items in order of decreasing size, where each item is placed into the lowest numbered bin in which it will fit. This paper explores our hypothesis that, while the solutions produced by priority algorithms are typically quite good, there are often better solutions ``nearby'' that can be found with small computational effort. Our hypothesis yields a natural and generic approach to extend priority algorithms to yield better solutions given additional running time. This approach uses the priority algorithm's ordering as a hint for how to explore the space of possible orderings. In particular, our algorithm uses the priority algorithm's placement rule to evaluate orderings that are close to the original ordering based on the Kendall-tau distance, also known as the BubbleSort distance.
Outside Collaborations: This work is done in collaboration with Harvard University.
Contact: Joseph Katz
Technology Area: Artificial Intelligence
Modification Date: September 12, 2007
