EUVIMEDEUVIMED entdecken
Crossref

Branch-and-Bound Algorithms as Polynomial-Time Approximation Schemes

Koppány István Encz, Monaldo Mastrolilli, Eleonora Vercesi

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →