Submodular Welfare under Routing Coupling: A Hierarchical Decomposition with Perturbation Guarantees
Abstract
This paper studies joint submodular welfare maximization and routing over graphs, where agents select items under diminishing returns and transport them through a network with congestion-dependent costs. Although welfare maximization admits matroid-based approximations and routing reduces to shortest paths under modular costs, their coupling creates supermodular interactions that break separability. We show that, for fixed routing, the objective remains submodular in the allocation variable, enabling a principled decomposition. Building on this property, we propose the Welfare-based Hierarchical Routing Algorithm (WHIRL), which alternates between tractable routing and allocation updates. Routing is initialized through its modular counterpart, while supermodular effects are modeled as bounded perturbations. The method has finite convergence guarantees and approximation bounds that depend explicitly on the deviation from modular routing. Numerical results illustrate the impact of routing-induced coupling and show that WHIRL achieves a favorable tradeoff between solution quality and computational cost.
Related
- From Consensus-Based Optimization to Particle Swarm Optimization: Convergence Guarantees under Drift-Diffusion Coupling
- An Efficient Randomized Hierarchical Tucker Decomposition
- A Benders decomposition approach for hierarchical k-medoids
- Average-Reward Reinforcement Learning for Multichain MDPs: A Hierarchical Decomposition Approach
- Hierarchical Majority Decomposition for Imbalanced Classification: A Recursive Binary Majority-Class Tree with Persistent Minority Comparison
BibTeX
@misc{gallart2026submodular,
title = {{Submodular Welfare under Routing Coupling: A Hierarchical Decomposition with Perturbation Guarantees}},
author = {Joan Vendrell Gallart and Nhat-Minh Tang-Nguyen and Alan Kuhnle and Solmaz Kia},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.07767},
eprint = {2609.07767},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.07767},
}
RIS
TY - UNPB
TI - Submodular Welfare under Routing Coupling: A Hierarchical Decomposition with Perturbation Guarantees
AU - Joan Vendrell Gallart
AU - Nhat-Minh Tang-Nguyen
AU - Alan Kuhnle
AU - Solmaz Kia
PY - 2026
DA - 2026/09/07
PB - arXiv
DO - 10.48550/arxiv.2609.07767
UR - https://arxiv.org/abs/2609.07767
AB - This paper studies joint submodular welfare maximization and routing over graphs, where agents select items under diminishing returns and transport them through a network with congestion-dependent costs. Although welfare maximization admits matroid-based approximations and routing reduces to shortest paths under modular costs, their coupling creates supermodular interactions that break separability. We show that, for fixed routing, the objective remains submodular in the allocation variable, enabling a principled decomposition. Building on this property, we propose the Welfare-based Hierarchical Routing Algorithm (WHIRL), which alternates between tractable routing and allocation updates. Routing is initialized through its modular counterpart, while supermodular effects are modeled as bounded perturbations. The method has finite convergence guarantees and approximation bounds that depend explicitly on the deviation from modular routing. Numerical results illustrate the impact of routing-induced coupling and show that WHIRL achieves a favorable tradeoff between solution quality and computational cost.
ER -