BALANCED BISUBMODULAR SYSTEMS AND BIDIRECTED FLOWS

スポンサーリンク

概要

• 論文の詳細を見る

• For a nonempty finite set V let 3^v be the set of all the ordered pairs of disjoint subset,s of V, i.e., 3^v := {(X, Y) | X, Y ⊆ V,X ∩ Y = ∅}. We define two operations, reduced union ⊔ and intersection ⊓, on 3^v as follows: for each (X_i,Y_i) ∈ 3^v (i = 1,2) (Y_l, Y_1) ⊔ (X_2, Y_2) = ((X_1 ∪ X_2) - (Y_1 ∪ Y_2), (Y_1 ∪ Y_2) - (X_1 ∪ X_2)), (X_1 , Y_1) ⊓ (X_2, Y_2) = (X_1 ∩ X_2, Y_1 ∩ Y_2). Also, for a {⊔, ⊓}-closed family F ⊆ 3^v a function f:F → R is called bisubmodular if for each (X_i , Y_i) ∈ F (i = 1, 2) we have f (X_1 ,Y_1) + f (X_2, Y_2) ≥ f((X_1, Y_1) ⊔ (X_2, Y_2)) + f ((X_1, Y_1) ⊓ (X_2, Y_2)). For a {⊔, ⊓}-closed family F ⊆ 3^V with (∅, ∅) ∈ F and a so-called bisubmodular function f : F → R on F with f(∅, ∅) = 0, the pair (F, 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 a base polyhedron of boundaries of an associated ordinary network.

• 社団法人日本オペレーションズ・リサーチ学会の論文

著者

• Ando Kazutoshi

  Institute Of Policy And Planning Scicnces University Of Tsukuba

• Ando Kazutoshi

  University Of Tsukuba

• Naitoh T

  Shiga Univ.

• Naitoh Takeshi

  Faculty Of Economics Shiga University

• Fujishige Satoru

  Division of Systems Science Department of Systems and Human Science Graduate School of Enginecring S

• 藤重 悟

  Kyoto University

関連論文

• THE MINIMUM-WEIGHT IDEAL PROBLEM FOR SIGNED POSETS
• BALANCED BISUBMODULAR SYSTEMS AND BIDIRECTED FLOWS
• A GREEDY ALGORITHM FOR MINIMIZING A SEPARABLE CONVEX FUNCTION OVER A FINITE JUMP SYSTEM
• A GREEDY ALGORITHM FOR MINIMIZING A SEPARABLE CONVEX FUNCTION OVER AN INTEGRAL BISUBMODULAR POLYHEDRON
• A TREE PARTITIONING PROBLEM ARISING FROM AN EVACUATION PROBLEM IN TREE DYNAMIC NETWORKS
• Optimal Sink Location Problem for Dynamic Flows in a Tree Network(Special Section on Discrete Mathematics and Its Applications)
• 劣モジュラ関数最小化のアルゴリズム:ブレイクスルーと周辺の話題 (特集 アルゴリズムの新展開--理論から工学へ)
• ANOTHER SIMPLE PROOF OF THE VALIDITY OF NAGAMOCHI AND IBARAKI'S MIN-CUT ALGORITHM AND QUEYRANNE'S EXTENSION TO SYMMETRIC SUBMODULAR FUNCTION MINIMIZATION
• STRUCTURES OF SUBLATTICES RELATED TO VEINOTT RELATION
• Algorithms for Submodular Flows(Special Issue on Algorithm Engineering : Surveys)
• Structures of Subpartitions Related to a Submodular Function Minimization

もっと見る 閉じる

スポンサーリンク