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: | Date Event 2006 Published |
| 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 |
| URI: | https://wrap.warwick.ac.uk/5247/ |
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 |