On Multiflow Lexicographics

✍ Scribed by Michael Lomonosov

• Book ID: 102570987
• Publisher: Elsevier Science
• Year: 2002
• Tongue: English
• Weight: 251 KB
• Volume: 23
• Category: Article
• ISSN: 0195-6698
• DOI: 10.1006/eujc.2002.0614

✦ Synopsis

Given an undirected Eulerian network with the terminal-set {s} ∪ T , we call a vector ξ = (ξ(t) : t ∈ T ) feasible if there exists an integer maximum multiflow having exactly ξ(t) (s, t)-paths for each t ∈ T . This paper contributes to describing the set of feasible vectors.

First, the feasible vectors are shown to be bases of a polymatroid (T, p) forming a proper part of the polytope defined by the supply-demand conditions; p(V ) = max{ξ(V ) : ξ ∈ }, V ⊆ T is described by a max-min theorem. The question whether contains all the integer bases, thereby admitting a polyhedral description, remains open. Second, the lexicographically minimum (and thereby maximum) feasible vector is found, for an arbitrary ordering of T .

The results are based on the integrality theorem of A. Karzanov and Y. Manoussakis (Minimum (2, r)-metrics and integer multiflows, Europ. J. Combinatorics (1996) 17, 223-232) but we develop an original approach, also providing an alternative proof to this theorem.