^March April – 2004 ^May

I will describe the problem of shortest paths in the Tower of Hanoi graph, i.e. shortest sequences of moves in the Tower of Hanoi puzzle leading from one legal disc configuration to another. The well-known special case of moving all the discs from one peg to another is an easy example, but the general case of arbitrary initial and terminal positions leads to an interesting algorithmic design problem. My recent solution involves the construction of a "tiebreaker" finite automaton that determines whether the largest disc will move once, or twice. As an application, I will calculate the average distance 466/885 between two randomly chosen points on the Sierpinski gasket (a.k.a. Sierpinski triangle) of unit side.

This is the second of 2-3 lectures in which we relate the asymptotics of the first rows in a partition via representation thoery to some special coverings of the sphere by Riemann surfaces. The lecture is independent of last week's lecture.

The local ratio technique is a methodology for the design and analysis of algorithms for a broad range of optimization problems. The technique is simple and elegant, and yet can be applied to many classical and fundamental problems (including covering problems, packing problems, and scheduling problems). The local ratio technique uses elementary math and requires combinatorial insight into the structure and properties of the problem at hand. Typically, when using the technique, one has to invent a weight function for a problem instance under which every ``reasonable'' solution is ``good.''

In this talk we introduce the local ratio technique and demonstrate its use in the design and analysis of algorithms for various problems. In particular, we present the first local ratio algorithm that uses negative weights. We also show that the local ratio technique is closely related to the primal-dual schema, though it is not based on LP duality.