2026-08-05T05:31:46Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23450 2025-06-30T07:23:10Z ddc:004 open_access

Branch-And-Bound Algorithms as Polynomial-Time Approximation Schemes Encz, Koppány István Mastrolilli, Monaldo Vercesi, Eleonora Branch-and-bound algorithm Polynomial-time approximation scheme Parallel machine scheduling problem Knapsack problem 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 behaviour, yielding increasingly better solutions within polynomial time. Our findings are supported by computational experiments and comparisons with benchmark methods. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Koppány István Encz and Monaldo Mastrolilli and Eleonora Vercesi 2025 Is Part Of LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2025.73 urn:nbn:de:0030-drops-234502 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.73 eng https://creativecommons.org/licenses/by/4.0/legalcode