Tuesday, February 1, 2011

SODA: Instance Optimality

The highlight of SODA for me was the plenary talk Computational Geometry for Non-Geometers by Timothy Chan, especially the part in which he discussed instance optimality. The basic idea is to consider algorithm analyses that take all inputs into account and operate optimally over all inputs in comparison to an algorithm designed specifically for that input (but not for that input's order). I believe this was first considered in a geometric setting (Instance-Optimal Geometric Algorithms), so you could imagine that the input is a set of points and the algorithm you're competing against doesn't know in advance in what order the points will be given to you. This wonderfully fixes the problem with worst-case analyses in which an algorithm might perform poorly on most input instances but there is some hard instance for which the performance is reasonable. Instead, under an instance-optimal analysis, the algorithm is expected to perform well on all input instances.

In the study of data structures for moving objects, a similar idea known as motion sensitivity was previously introduced under a motion-specific setting. Motion sensitivity generally describes algorithms that perform well under orderly motion and have performance that degrades as the point motion becomes more random. In my own work, I consider entropy-based analyses in order to capture this concept. In fact, the instance-optimal analysis Timothy described also resulted in an entropy-like inequality, so perhaps this relationship is inevitable/necessary for these analyses.

It's an exciting new area that I'm hoping to see a lot more of. It was certainly an excellent talk.


daveagp said...

The same notion of optimality has been studied in distributed computing too, called "universal optimality" when I have seen it.

But, it is not such a hard concept to imagine, the remarkable thing is if you can actually find an algorithm that has such a property.

I have a paper from ICALP 2008 which got a distributed algorithm for finding all 2-edge cuts of a graph in O(Diameter) time, which has this property; the paper which I cited as the earliest I could find saying "universally optimal" is

Juan A. Garay, Shay Kutten, and David Peleg. A sublinear time distributed algorithm for
minimum-weight spanning trees. SIAM J. Comput., 27(1):302–316, 1998. Preliminary version
appeared in Proc. 34th FOCS, pages 659–668, 1993

sorelle said...

Ooooh, thanks for the reference!