Speaker: Alex Lopez-Ortiz
Consider the scenario of routing of a Fedex delivery van. The packages to be delivered are received by midnight and delivery starts at 7:00am. This means we have seven hours to compute the best possible approximation to the optimum Travelling Salesman Path computable in that time.Contract algorithms are used in this setting. A contract algorithm is an algorithm that takes the amount of available computing time along with the input and produces a solution of quality conmensurate with this amount of time.
An interruptible algorithm is another variant of anytime algorithms in which the solution can be requested at any time. An example of an interruptible algorithm is a branch and bound backtracking search which keeps track of the "best" solution seen so far and returns the running best as the answer whenever interrupted.
Branch and bound interruptible algorithms are generally easy to program, but difficult to measure the quality of the solution they produce. In contrast, polynomial time approximation schemes provide a ready-made library of contract algorithms with known approximation factors.
In this talk we show how to optimally schedule a set of contract algorithms to simulate an iterruptible algorithm on a given a number of available computers.
This is joint work with Angele Hamel and Spyros Angelopolous to appear in AAAI 2006.
Food: Greg Hines