| Mittagsseminar Talk Information | |
Date and Time: Tuesday, May 30, 2006, 12:15 pm Duration: This information is not available in the database Location: This information is not available in the database Speaker: Stefan Geisseler Overhang
By M. Paterson and U. Zwick (ACM-SIAM Symposium on Discrete Algorithms (SODA'06))
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/2Hn, where
Hn = ∑ni=1 1/i ~ ln n
is the nth harmonic number, by stacking all the blocks one on top of another
with the ith block from the top displaced by 1/2i beyond the block below.
This solution is widely believed to be optimal. We show that it is exponentially far from
optimal by giving explicit constructions with an overhang of Ω(n1/3).
We also prove some upper bounds on the overhang that can be achieved. The stability of
a given stack of blocks corresponds to the feasibility of a linear program and so can
be efficiently determined.
Upcoming talks | All previous talks | Talks by speaker |  Upcoming talks in iCal format (beta version!) Previous talks by year: 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996 Information for students and suggested topics for student talks
Automatic MiSe System Software Version 1.3392 | admin login
|
