prowadzi: Uri Zwick
- Speaker(s)
- Uri Zwick
- Affiliation
- Tel Aviv University
- Date
- March 8, 2007, 12:15 p.m.
- Room
- room 5870
- Seminar
- Seminar Algorithms
How far off the edge of the table can we reach by stacking n
identical blocks of length 1? A classical solution achieves an
overhang of (1/2)H_n, where H_n=1/1+1/2+...+1/n is the n-th harmonic
number. This solution is widely believed to be optimal. We show,
however, that it is exponentially far from optimal by giving explicit
constructions with an overhang of Omega(n^{1/3}). Together with
Yuval Peres, Mikkel Thorup and Peter Winkler, we have recently
shown that no larger overhangs are achievable.