A GREEDY ALGORITHM FOR MINIMIZING A SEPARABLE CONVEX FUNCTION OVER A FINITE JUMP SYSTEM
スポンサーリンク
概要
- 論文の詳細を見る
We present a greedy algorithm for minimizing a separable convex function over a finite jump system (E,f), where E is a nonempty finite set and f is a nonempty finite set of integral points in Z^E satisfying a certain exchange axiom. The concept of jump system was introduced by A. Bouchet and W. H. Cunningham. A jump system is a generalization of an integral bisubmodular polyhedron, an integral polymatroid, a (poly-)pseudomatroid and a delta-matroid, and has combinatorially nice properties. The algorithm starts with an arbitrary feasible solution and a current feasible solution incrementally moves toward an optimal one in a greedy way. We also show that the greedy algorithm terminates after changing an initial feasible solution at most[numerical formula] times, where for each e ∈ E [numerical formula].
- 社団法人日本オペレーションズ・リサーチ学会の論文
著者
-
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
Institute of Policy and Planning Sciences University of Tsukuba
-
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)
- An Almost-Linear-Time Algorithm for Solving the Graph-Realization Problem (Graphs and Combinatorics III)
- Structures of Subpartitions Related to a Submodular Function Minimization
- A DUAL ALGORITHM FOR FINDING THE MINIMUM-NORM POINT IN A POLYTOPE
- A DUAL ALGORITHM FOR FINDING A NEAREST PAIR OF POINTS IN TWO POLYTOPES
- AN EFFICIENT COST SCALING ALGORITHM FOR THE INDEPENDENT ASSIGNMENT PROBLEM