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.

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 > 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
Date:	2006
Number of Pages:	10
Page Range:	pp. 231-240
Identification Number:	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:	http://wrap.warwick.ac.uk/id/eprint/5247

Data sourced from Thomson Reuters' Web of Knowledge

Request changes to a record

Actions (login required)

View Item