最小費用流問題のためのネットワーク単体擬乗数アルゴリズムの計算実験

6 References
  • SAKUTA Izumi
    Mathematical Engineering and Information Physics Course Division of Engineering, Graduate School, University of Tokyo

Bibliographic Information

Other Title
  • Computational Testing of the Network Simplex Premultiplier Algorithm for Minimum Cost Flow Problems

Search this article

Description

最小費用流問題はネットワーク最適化における最も基本的な問題の一つである. 最小費用流問題を解く, 多くの優れた多項式時間のアルゴリズムがあるが, 実用的にはそのインプリメントの簡単さと速さの両面から, ネットワーク単体法が広く用いられている. その実用性に反して, 最近まで理論的には主ネットワーク単体法のピボット数は多項式でおさえられていなかった. 擬乗数法は最近 Orlin によって開発された, 最小費用流問題に対する初の多項式時間主ネットワーク単体法である. 本稿では, この新しい算法をいくつかの方法でインプリメントし, その振舞いを示す.
The minimum cost flow problem is one of the most fundamental problems in network optimization. There are a number of distinguished polynomial-time algorithms for it. Practically, however, the network simplex algorithm is chosen due to its simplicity and speed. Despite its practicality, there was no theoretical polynomial bound for the number of pivots in the primal network simplex algorithm until recently. The premultiplier algorithm is the first polynomial primal network simplex algorithm for the minimum cost flow problem proposed recently by Orlin. In this report, I implement this new algorithm in several ways and show the performance.

Journal

  • IPSJ SIG Notes

    IPSJ SIG Notes 50 25-32, 1996-03-15

    Information Processing Society of Japan (IPSJ)

References(6)*help

See more

Details 詳細情報について

  • CRID
    1574231876907391232
  • NII Article ID
    110002812219
  • NII Book ID
    AN1009593X
  • ISSN
    09196072
  • Text Lang
    en
  • Data Source
    • CiNii Articles

Report a problem

Back to top