# Balanced bisubmodular systems and bidirected flows

0.00 Avg rating0 Votes
 Article ID: iaor19981926 Country: Japan Volume: 40 Issue: 3 Start Page Number: 437 End Page Number: 447 Publication Date: Sep 1997 Journal: Journal of the Operations Research Society of Japan Authors: Fujishige Satoru, Naitoh Takeshi, Ando Kazutoshi Keywords: networks, optimization
Abstract:

For a nonempty finite set V let 3V be the set of all the ordered pairs of disjoint subsets of V, i.e. 3V = {(X,Y)|X,Y ⊆ V,X ∩ Y = ∅}. We define two operations, reduced union ⊔ and intersection ⊓, on 3V as follows: for each (Xi,Yi) ∈ 3V (i = 1,2) (X1,Y1) ⊔ (X2, Y2) = ((X1 ∪ X2) – (Y1 ∪ Y2), (Y1 ∪ Y2) – (X1 ∪ X2)), (X1,Y1) ⊓ (X2,Y2) = (X1 ∩ X2,Y1 ∩ Y2). Also, for a {⊔,⊓}-closed family ℱ ⊆ 3V a function f : ℱ → R is called bisubmodular if for each (Xi,Yi) ∈ ℱ (i = 1,2) we have f(X1,Y1) + f(X2,Y2) ≥ f((X1,Y1) ⊔ (X2,Y2)) + f((X1,Y1) ⊓ (X2,Y2)). For a {⊔,⊓}-closed family ℱ ⊆ 3V with (∅,∅) ∈ ℱ and a so-called bisubmodular function f : ℱ → R on ℱ with f(∅,∅) = 0, the pair (ℱ, f) is called a bisubmodular system on V. In this paper we consider two classes of bisubmodular systems which are closely related to base polyhedra. The first one is the class of balanced bisubmodular systems. We give a characterization of balanced bisubmodular systems and show that their associated polyhedra are the convex hulls of reflections of base polyhedra. The second one is that of cut functions of bidirected networks. It is shown that the polyhedron determined by the cut function of a bidirected network is the set of the boundaries of flows in the bidirected network and is a projection of a section of base polyhedron of boundaries of an associated ordinary network.

## Reviews

Required fields are marked *. Your email address will not be published.