Branch-and-Bound Algorithms as Polynomial-Time Approximation Schemes
研究显示，分支定界算法在背包和调度问题中能像多项式时间近似方案一样，在多项式时间内给出越来越好的解，并通过实验验证了其有效性。
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”)].