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

2025/04/22 by Encz, Koppány István, Mastrolilli, Monaldo, Vercesi, Eleonora · 2 voices
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2504.15885

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. This paper is an extended version of a paper accepted at ICALP 2025

Discussions

• Along these lines? arxiv.org/abs/2504.15885 [bsky, 8 points, 1 comments]
• The extended version of our #ICALP2025 paper is now online! We try to partially bridge this gap by showing that, given certain rules for node selection, branching and bounding branch-and-bound algorit [bsky, 6 points, 0 comments]

Related

• Branch-and-Bound versus Lift-and-Project Relaxations in Combinatorial Optimization
• The Branch-and-Bound Tree Closure
• Analyzing Branch-and-Bound Algorithms for the Multiprocessor Scheduling\n Problem
• Adapting Branching and Queuing for Multi-objective Branch and Bound
• A PTAS for Scheduling with Tree Assignment Restrictions