arbiter
JournalsAccount

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

Koppány István Encz et al.

Mathematics of Operations Research2026https://doi.org/10.1287/moor.2025.1183article
AJG 3ABDC A
Weight
0.50

Abstract

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”)].

Open via your library →

Cite this paper

https://doi.org/https://doi.org/10.1287/moor.2025.1183

Or copy a formatted citation

@article{koppány2026,
  title        = {{Branch-and-Bound Algorithms as Polynomial-Time Approximation Schemes}},
  author       = {Koppány István Encz et al.},
  journal      = {Mathematics of Operations Research},
  year         = {2026},
  doi          = {https://doi.org/https://doi.org/10.1287/moor.2025.1183},
}

Paste directly into BibTeX, Zotero, or your reference manager.

Flag this paper

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

Flags are reviewed by the Arbiter methodology team within 5 business days.

Evidence weight

0.50

Balanced mode · F 0.40 / M 0.15 / V 0.05 / R 0.40

F · citation impact0.50 × 0.4 = 0.20
M · momentum0.50 × 0.15 = 0.07
V · venue signal0.50 × 0.05 = 0.03
R · text relevance †0.50 × 0.4 = 0.20

† Text relevance is estimated at 0.50 on the detail page — for your query’s actual relevance score, open this paper from a search result.