Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2602.11366 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918333495902208 |
|---|---|
| author | Gmeiner, Simon Schulz, Andreas S. |
| author_facet | Gmeiner, Simon Schulz, Andreas S. |
| contents | How can a stack of identical blocks be arranged to extend beyond the edge of a table as far as possible? We consider a generalization of this classic puzzle to blocks that differ in width and mass. Despite the seemingly simple premise, we demonstrate that it is unlikely that one can efficiently determine a stack configuration of maximum overhang. Formally, we prove that the Block-Stacking Problem is NP-hard, partially answering an open question from the literature. Furthermore, we demonstrate that the restriction to stacks without counterweights has a surprising connection to the Airplane Refueling Problem, another famous puzzle, and to Robust Appointment Scheduling, a problem of practical relevance. In addition to revealing a remarkable relation to the real-world challenge of devising schedules under uncertainty, their equivalence unveils a polynomial-time approximation scheme, that is, a $(1+ε)$-approximation algorithm, for Block Stacking without counterbalancing and a $(2+ε)$-approximation algorithm for the general case. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_11366 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Block Stacking, Airplane Refueling, and Robust Appointment Scheduling Gmeiner, Simon Schulz, Andreas S. Combinatorics Computational Complexity 90C27 How can a stack of identical blocks be arranged to extend beyond the edge of a table as far as possible? We consider a generalization of this classic puzzle to blocks that differ in width and mass. Despite the seemingly simple premise, we demonstrate that it is unlikely that one can efficiently determine a stack configuration of maximum overhang. Formally, we prove that the Block-Stacking Problem is NP-hard, partially answering an open question from the literature. Furthermore, we demonstrate that the restriction to stacks without counterweights has a surprising connection to the Airplane Refueling Problem, another famous puzzle, and to Robust Appointment Scheduling, a problem of practical relevance. In addition to revealing a remarkable relation to the real-world challenge of devising schedules under uncertainty, their equivalence unveils a polynomial-time approximation scheme, that is, a $(1+ε)$-approximation algorithm, for Block Stacking without counterbalancing and a $(2+ε)$-approximation algorithm for the general case. |
| title | Block Stacking, Airplane Refueling, and Robust Appointment Scheduling |
| topic | Combinatorics Computational Complexity 90C27 |
| url | https://arxiv.org/abs/2602.11366 |