Overhang

DOI10.1145/1109557.1109584MaRDI QIDQ3581532zbMATH OpenOpenAlexWikidataFDO

Authors Uri Zwick, Mike Paterson

Publication date 16 August 2010

Published in Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0710.2357

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to sequences, series, summability (40-02) Nonnumerical algorithms (68W05)

Abstract: How far off the edge of the table can we reach by stacking $n$ identical, homogeneous, frictionless blocks of length 1? A classical solution achieves an overhang of $1/2H_n$, where $H_{n}lnn$ is the $n$th harmonic number. This solution is widely believed to be optimal. We show, however, that it is, in fact, exponentially far from optimality by constructing simple $n$-block stacks that achieve an overhang of $c{n}^{1/3}$, for some constant $c>0$.

Cited in

(3)

• Overpals, underlaps, and underpals
• Overtaking VEST
• Hybrid planning for challenging construction problems: an answer set programming approach

This page was built for publication: Overhang

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3581532)