AN EFFICIENT COST SCALING ALGORITHM FOR THE INDEPENDENT ASSIGNMENT PROBLEM

スポンサーリンク

概要

• 論文の詳細を見る

• An efficient cost scaling algorithm is presented for the independent assignment problem of Iri and Tomizawa, which is equivalent to the weighted matroid intersection problem of Edmonds. Our algorithm in general can be viewed as a generalization of Orlin and Ahuja's scaling algorithm for the ordinary assignment problem. On a bipartite graph with n vertices and integer arc costs bounded by C, an optimal r-independent assignment can be found in O(√<rgt:n^2 log(rC)) time by our algorithm under an independence oracle for matorids.

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

著者

• Fujishige Satoru

  Institute of Policy and Planning Sciences University of Tsukuba

• Fujishige Satoru

  Institute Of Socio-economics Planning University Of Tsukuba

• Xiaodong Zhang

  Institute Of Socio-economics Planning University Of Tsukuba

関連論文

• THE MINIMUM-WEIGHT IDEAL PROBLEM FOR SIGNED POSETS
• A GREEDY ALGORITHM FOR MINIMIZING A SEPARABLE CONVEX FUNCTION OVER A FINITE JUMP SYSTEM
• An Almost-Linear-Time Algorithm for Solving the Graph-Realization Problem (Graphs and Combinatorics III)
• 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

スポンサーリンク