Paterson, Mike and Zwick, Uri (2006) Overhang. In: 17th ACM-SIAM Symposium on Discrete Algorithms, Miami, FL, JAN, 2006. Published in: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms pp. 231-240.Full text not available from this repository.
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 = Sigma(n)(i=1) 1/i similar to In n is the n(th) harmonic number, by stacking all the blocks one on top of another with the 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 Omega(n(1/3)). We also prove some upper bounds on the overhang that can lie achieved. The stability of a given stack of blocks corresponds to the feasibility of a linear program and so can be efficiently determined.
|Item Type:||Conference Item (Paper)|
|Subjects:||Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Q Science > QA Mathematics
|Divisions:||Faculty of Science > Computer Science|
|Journal or Publication Title:||Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms|
|Number of Pages:||10|
|Page Range:||pp. 231-240|
|Access rights to Published version:||Restricted or Subscription Access|
|Conference Paper Type:||Paper|
|Title of Event:||17th ACM-SIAM Symposium on Discrete Algorithms|
|Type of Event:||Other|
|Location of Event:||Miami, FL|
|Date(s) of Event:||JAN, 2006|
Actions (login required)