Exact Algorithms for Resource Reallocation Under Budgetary Constraints

arXiv:2602.18438v1 Announce Type: new
Abstract: Efficient resource (re-)allocation is a critical challenge in optimizing productivity and sustainability within multi-party supply networks. In this work, we introduce the textsc{Red-Blue Reinforcement} (R-BR) problem, where a service provider under budgetary constraints must minimize client reallocations to reduce the required number of servers they should maintain by a specified amount. We conduct a systematic algorithmic study, providing three exact algorithms that scale well as the input grows (FPT), which could prove useful in practice. Our algorithms are efficient for topologies that model rural road networks (bounded distance to cluster), modern transportation systems (bounded modular-width), or have bounded clique-width, a parameter that is of great theoretical importance.