prowadzi: Uri Zwick

Speaker(s)

Uri Zwick

Affiliation

Tel Aviv University

Date

March 8, 2007, 12:15 p.m.

Room

room 5870

Title in Polish

Overhang

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.

---