Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2606.01684 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
Sommario:
- The theory of submodular flows, introduced by Edmonds and Giles, is a cornerstone of combinatorial optimization, unifying network flows, matroid intersections and directed cut coverings. In this paper, we establish a measurable-space version of this framework, addressing the structural existence and duality questions raised as part of Problem~10.6 by Lovász in \textit{Submodular setfunctions on sigma-algebras, version 2}. We develop a theory of submodular flows on standard Borel spaces and establish the measurable analogues of the existence and optimality theorems. Furthermore, we introduce a measurable notion of the residual graph and characterize extreme flows by combining a base-polytope intersection condition with an acyclicity condition for the measurable residual graph, generalizing the discrete geometric intuition to the infinite-dimensional setting. Finally, we apply the theory to constrained supply-demand problems on measurable bipartite graphs and to fractional measurable orientations.