Search Results

Documents authored by Vercesi, Eleonora

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.73
Branch-And-Bound Algorithms as Polynomial-Time Approximation Schemes

Authors: Koppány István Encz, Monaldo Mastrolilli, and Eleonora Vercesi

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

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 behaviour, yielding increasingly better solutions within polynomial time. Our findings are supported by computational experiments and comparisons with benchmark methods.
Cite as

Koppány István Encz, Monaldo Mastrolilli, and Eleonora Vercesi. Branch-And-Bound Algorithms as Polynomial-Time Approximation Schemes. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 73:1-73:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{encz_et_al:LIPIcs.ICALP.2025.73,
  author =	{Encz, Kopp\'{a}ny Istv\'{a}n and Mastrolilli, Monaldo and Vercesi, Eleonora},
  title =	{{Branch-And-Bound Algorithms as Polynomial-Time Approximation Schemes}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{73:1--73:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.73},
  URN =		{urn:nbn:de:0030-drops-234502},
  doi =		{10.4230/LIPIcs.ICALP.2025.73},
  annote =	{Keywords: Branch-and-bound algorithm, Polynomial-time approximation scheme, Parallel machine scheduling problem, Knapsack problem}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact