Max-balanced flows in oriented matroids

✍ Scribed by Mark Hartmann; Michael H. Schneider

• Publisher: Elsevier Science
• Year: 1995
• Tongue: English
• Weight: 863 KB
• Volume: 137
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(93)e0168-4

✦ Synopsis

Let M =(E, d~) be an oriented matroid on the ground set E. A real-valued vector x defined on E is a max-balanced flow for M if for every signed cocircuit Y~(.9 ±, we have maxe~y+xe=maxe~r-x e. We extend the admissibility and decomposition theorems of Hamacher from regular to general oriented matroids in the case of max-balanced flows, which gives necessary and sufficient conditions for the existence of a max-balanced flow x satisfying l ~< x ~< u. We further investigate the semilattice of such flows under the usual coordinate partial order, and obtain structural results for the minimal elements. We also give necessary and sufficient conditions for the existence of such a flow when we are allowed to reverse the signs on a subset F_~ E. The proofs of all of our results are constructive, and yield polynomial algorithms in case M is coordinatized by a rational matrix A. In this same setting, we describe a polynomial algorithm that for a given vector w defined on E, either finds a potential p such that w'= w + pA is max-balanced, or a certificate that M has no max-balanced flow.