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

Koppány István Encz, Monaldo Mastrolilli, Eleonora Vercesi

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 th…