The Library
Maximum overhang
Tools
Tools
Tools
Paterson, Michael S., Peres, Yuval, Thorup, Mikkel, Winkler, Peter and Zwick, Uri (2008) Maximum overhang. In: 19th ACM-SIAM Symposium on Discrete Algorithms, San Francisco, CA, Jan 20-22, 2008. Published in: Proceedings of the 19th Annual ACM - SIAM Symposium on Discrete Algorithms pp. 756-765. ISBN 978-0-898716-47-4.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dl.acm.org/citation.cfm?id=1347165&CFID=672...
Abstract
How far can a stack of n identical blocks be made to hang over the edge of a table? The question dates back to at least the middle of the 19th century and the answer to it was widely believed to be of order log n. However, at SODA'06, Paterson and Zwick constructed n-block stacks with overhangs of order n(1/3). Here we complete the solution to the overhang problem, and answer Paterson and Zwick's primary open question, by showing that order n(1/3) is best possible. At the heart of the argument is a lemma (possibly of independent interest) showing that order d(3) non-adaptive coinflips are needed to propel a discrete random walk on the number line to distance d.
We note that our result is not a mainstream algorithmic result, yet it is about the solution to a discrete optimization problem. Moreover, it illustrates how methods founded in theoretical computer science can be applied to a problem that has puzzled some mathematicians and physicists for more than 150 years.
| Item Type: | Conference Item (UNSPECIFIED) | ||||
|---|---|---|---|---|---|
| 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 19th Annual ACM - SIAM Symposium on Discrete Algorithms | ||||
| Publisher: | SIAM | ||||
| ISBN: | 978-0-898716-47-4 | ||||
| Official Date: | 2008 | ||||
| Dates: |
|
||||
| Number of Pages: | 10 | ||||
| Page Range: | pp. 756-765 | ||||
| Status: | Not Peer Reviewed | ||||
| Publication Status: | Published | ||||
| Access rights to Published version: | Restricted or Subscription Access | ||||
| Title of Event: | 19th ACM-SIAM Symposium on Discrete Algorithms | ||||
| Type of Event: | Conference | ||||
| Location of Event: | San Francisco, CA | ||||
| Date(s) of Event: | Jan 20-22, 2008 |
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 |
