Overhang

Prelegent(ci)

Uri Zwick

Afiliacja

Tel Aviv University

Termin

8 marca 2007 12:15

Pokój

p. 5870

Tytuł w języku angielskim

prowadzi: Uri Zwick

Seminarium

Seminarium "Algorytmika"

---

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.

---