Branch-and-Bound Algorithms as Polynomial-time Approximation Schemes
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866910095304032256 |
|---|---|
| author | Encz, Koppány István Mastrolilli, Monaldo Vercesi, Eleonora |
| author_facet | Encz, Koppány István Mastrolilli, Monaldo Vercesi, Eleonora |
| contents | 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 |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_15885 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Branch-and-Bound Algorithms as Polynomial-time Approximation Schemes Encz, Koppány István Mastrolilli, Monaldo Vercesi, Eleonora Data Structures and Algorithms Optimization and Control 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 |
| title | Branch-and-Bound Algorithms as Polynomial-time Approximation Schemes |
| topic | Data Structures and Algorithms Optimization and Control |
| url | https://arxiv.org/abs/2504.15885 |