The Library
Overhang
Tools
Tools
Tools
Paterson, Michael S. 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. ISBN 978-0-89871-605-4. doi:10.1145/1109557.1109584 ISSN 9780898716054.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Abstract
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, Engineering and Medicine > Science > Computer Science | ||||
| Journal or Publication Title: | Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms | ||||
| Publisher: | SIAM | ||||
| ISBN: | 978-0-89871-605-4 | ||||
| ISSN: | 9780898716054 | ||||
| Official Date: | 2006 | ||||
| Dates: |
|
||||
| Number of Pages: | 10 | ||||
| Page Range: | pp. 231-240 | ||||
| DOI: | 10.1145/1109557.1109584 | ||||
| Status: | Peer Reviewed | ||||
| Publication Status: | Published | ||||
| 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 |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
