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

• 成果类型: Article; Early Access
• 署名作者: Encz, Koppany Istvan; Mastrolilli, Monaldo; Vercesi, Eleonora
• 署名单位: Universita della Svizzera Italiana
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X; 1526-5471
• DOI: 10.1287/moor.2025.1183
• 发表日期: 2026-03-31
• 关键词: branch-and-bound algorithm; polynomial-time approximation scheme; parallel machine scheduling problem; knapsack problem; MACHINE SCHEDULING PROBLEMS; Knapsack

摘要

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 PTASlike behavior, yielding increasingly better solutions within polynomial time. Our findings are supported by computational experiments and comparisons with benchmark methods.