Branch-and-Bound Algorithms as Polynomial-Time Approximation Schemes
Mathematics of Operations Research · 31.03.2026
DOI: 10.1287/moor.2025.1183 ↗Kurz gefasst
Fachartikel in der Zeitschrift Mathematics of Operations Research, online erschienen am 31.03.2026. Verfasst von Koppány István Encz und 2 weiteren Autor:innen. Die Arbeit nennt 48 Literaturangaben.
Abstract (Originalsprache)
Branch-and-bound algorithms (B&B) and polynomial-time approximation schemes (PTAS) are two seemingly distant areas of combinatorial optimization. We intend to (partially) bridge the gap between them while expanding the boundary of theoretical knowledge on the B&B framework. Branch-and-bound algorithms typically guarantee that an optimal solution is eventually found. However, we show that the standard implementation of branch-and-bound for certain knapsack and scheduling problems also exhibits PTAS-like behavior, yielding increasingly better solutions within polynomial time. Our findings are supported by computational experiments and comparisons with benchmark methods. Funding: This work was supported by Schweizerischer Nationalfonds zur Förderung der Wissenschaftlichen Forschung [Grant 200021_212929/1 (“Computational methods for integrality gaps analysis”)].
Zitieren
APA
Encz, K. I., Mastrolilli, M., & Vercesi, E. (2026). Branch-and-Bound Algorithms as Polynomial-Time Approximation Schemes. Mathematics of Operations Research. https://doi.org/10.1287/moor.2025.1183
Vancouver
Encz KI, Mastrolilli M, Vercesi E. Branch-and-Bound Algorithms as Polynomial-Time Approximation Schemes. Mathematics of Operations Research. 2026. doi:10.1287/moor.2025.1183
BibTeX
@article{Encz2026,
author = {Encz, Koppány István and Mastrolilli, Monaldo and Vercesi, Eleonora},
title = {Branch-and-Bound Algorithms as Polynomial-Time Approximation Schemes},
journal = {Mathematics of Operations Research},
year = {2026},
doi = {10.1287/moor.2025.1183}
}
EUVIMED