Submodular Welfare under Routing Coupling: A Hierarchical Decomposition with Perturbation Guarantees

Joan Vendrell Gallart, Nhat-Minh Tang-Nguyen, Alan Kuhnle, Solmaz Kia

arXivarxiv/2609.07767Sep 7, 2026math.OCscore 0

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…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2609.07767
curl -X POST /api/v1/records/arxiv/2609.07767/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.07767/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'