2026-07-23T08:19:13Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23262 2025-07-15T15:33:54Z ddc:004 open_access

A New Relaxation for Tree-Based Problems and Minimum Power-Cost Spanning Trees Marianczuk, Luzie Althaus, Ernst Irnich, Stefan Pfetsch, Marc E. lower bounds symmetric connectivity power range assignment dynamic programming optimal substructure In this paper, we investigate lower bounds of tree-based optimization problems in order to obtain effective exact algorithms, such as branch-and-bound algorithms. Our new approach inherits the development of dynamic programming algorithms for constrained shortest path problems, as they occur as subproblems in Lagrangian relaxation algorithms and column generation-based algorithms for variants of the Vehicle Routing Problem. In the q-route relaxation, paths must satisfy a capacity constraint while the elementarity constraint is relaxed, that is, paths may contain cycles. An analogue of q-routes for tree optimization problems are q-arbs, a structure that relaxes elementarity for arborescences. We introduce a generalized formulation of q-arbs for a broad class of tree-based problems, and apply the neighborhood restrictions of so-called ng-routes to them to obtain tighter bounds. We apply the new dynamic programming approach to the Minimum Power-Cost Spanning Tree Problem and show empirically that the resulting bounds are often better than traditional LP-based lower bounds of (mixed) integer programming models. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Luzie Marianczuk and Ernst Althaus and Stefan Irnich and Marc E. Pfetsch 2025 Is Part Of LIPIcs, Volume 338, 23rd International Symposium on Experimental Algorithms (SEA 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SEA.2025.24 urn:nbn:de:0030-drops-232620 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2025.24 eng https://creativecommons.org/licenses/by/4.0/legalcode