Inverse Polymatroidal Flow Problem

Mao-Cheng Cai (), Xiaoguang Yang () and Yanjun Li
Additional contact information
Mao-Cheng Cai: Academia Sinica
Xiaoguang Yang: Academia Sinica
Yanjun Li: Academia Sinica

Journal of Combinatorial Optimization, 1999, vol. 3, issue 1, No 9, 115-126

Abstract: Abstract Let D = (V, A) be a directed graph, for each vertex v ∈ V, let Δ+(v) and Δ− (v) denote the sets of arcs leaving and entering v, $${\mathcal{F}}_v^ +$$ and $${\mathcal{F}}_v^ -$$ be intersecting families on Δ+(v) and Δ−(v), respectively, and $$\rho _v^+ :{\mathcal{F}}_v^+ \to {\mathcal{R}}_+$$ and $$\rho_v^- :{\mathcal{F}}_v^+ \to {\mathcal{R}}_+$$ be submodular functions on intersecting pairs. A flow f : A → R is feasible if $$\begin{gathered} f(\Delta ^ + (v)) = f(\Delta ^ - (v)){\text{ }}\forall v \in V,\hfill \\ f(S) \leqslant \rho _v^ + (S){\text{ }}\forall S \in \mathcal{F}_v^+ ,v \in V, \hfill \\ f(S) \leqslant \rho _v^ - (S){\text{ }}\forall S \in \mathcal{F}_v^- ,v \in V, \hfill \\ f(e) \geqslant 0{\text{ }}\forall e \in A, \hfill \\\end{gathered}$$ Given a cost function c on A, the minimum cost polymatroidal flow problem is to find a feasible flow f with minimum cost σ{c(e)f(e)ve σ A}, it is a significant generalization of many combinatorial optimization problems. Given a feasible flow f*, cost and restriction functions on A, the inverse polymatroidal flow problem is to modify c, optimally and with bounds, such that f* becomes a minimum cost polymatroidal flow under the modified cost. It is shown in this paper that the inverse problem can be formulated as a combinatorial linear program and can be further transformed into a minimum cost circulation problem. Hence it can be solved efficiently by strongly polynomial combinatorial algorithms. We also give a necessary and sufficient condition for the feasibility of the inverse problem.

Keywords: inverse problem; polymatroidal flow; minimum cost circulation; combinatorial strongly polynomial algorithm (search for similar items in EconPapers)
Date: 1999
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1023/A:1009877408258 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:3:y:1999:i:1:d:10.1023_a:1009877408258

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1023/A:1009877408258

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().