Branch-and-Bound Algorithms as Polynomial-time Approximation Schemes
This work provides theoretical insights for combinatorial optimization researchers, though it appears incremental as it builds on existing branch-and-bound frameworks.
The paper tackles the gap between branch-and-bound algorithms and polynomial-time approximation schemes, showing that standard branch-and-bound implementations for knapsack and scheduling problems yield increasingly better solutions in polynomial time, with results supported by computational experiments.
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. This paper is an extended version of a paper accepted at ICALP 2025