無向ネットワークにおける流量要求を満たす施設配置問題
スポンサーリンク
概要
- 論文の詳細を見る
この論文では, 無向ネットワークにおいて, 各点vに対してd(v)の流量を送ることが可能な, 最小費用の点集合Sを発見する問題を扱う.この問題は一般的にはNP-困難であるが, 田村らは, 各点の費用が一定である特殊な場合の問題を解く貧欲解法を提案している.我々は線形計画双対性を用いて、この貧欲アルゴリズムにおける正当性のより単純な証明を与え, 計算時間をO(n^2M)からO(nM)へと改良する.ここでnはネットワークの点の数であり, Mはnの点とmの枝を持つネットワークにおける最大フローの計算時間を定義する.我々はまた, 一定の要求容量と任意の費用を持つ特殊な場合の問題を解くO(n(m+nlogn))のアルゴリズムを提案する.
- 一般社団法人情報処理学会の論文
- 2000-05-19
著者
-
岩田 覚
東京大学大学院工学系研究科計数工学専攻
-
牧野 和久
大阪大学大学院基礎工学研究科
-
新 浩治
大阪大学大学院基礎工学研究科システム人間系専攻システム科学分野
-
藤重 悟
大阪大学大学院基礎工学研究科システム人間系専攻システム科学分野
関連論文
- 双対制限された列挙問題 : 離散分布に対する交差不等式とその応用
- ラミナー被覆制約を持つ単調凹関数最小化問題
- 木構造の動的ネットワーク上の施設配置問題に対するO(nlog^2n)時間アルゴリズム
- An O(nlog^2n)Algorithm for the Optimal Sink Lacation Problem on Dynamic Tree Networks
- 1-B-6 線形計画問題の符号可解性(組合せ最適化(1))
- 符号対称行列のSylvester指数(組合せ最適化(6))
- M凸劣モジュラ流問題に対する容量スケーリング法
- 部分定義論理関数のホーン拡張について
- 閾グラフの最小辺ランキング全域木について
- 最小辺ランキング全域木問題について
- On Minimum Edge Ranking Spanning Trees
- Approximate- Weight-Splitting Algorithm for a Minimum Common Base of a Pair of Matroids(Mathematical Structure of Optimization Theory)
- マトロイドの最適共通基問題に対するオークション算法(グラフ・ネットワーク)
- 初等的フローゲームの凸性について(計算量理論とアルゴリズム論文小特集)
- フローゲームの凸性について(ゲーム理論(2))
- 第10回「整数計画法・組合せ最適化」国際会議(IPCO X)に参加して
- 劣モジュラ関数の最小化
- 双劣モジュラ関数最小化
- 無向ネットワークにおける流量要求を満たす施設配置問題
- 劣モジュラ関数最小化の強多項式時間アルゴリズム (新しいパラダイムとしてのアルゴリズム工学)
- 劣モジュラ関数最小化の強多項式時間アルゴリズム
- ネットワーク上の被覆型施設配置問題(グラフ・ネットワーク(3))
- 設備更改のスケジューリング問題への基本分割の応用(スケジューリング)
- 1-B-9 グラフの向き付けに関する最適化問題の解法(組合せ最適化(2))
- 正則コテリの効率的な列挙について
- 正則2部グラフに対する単純なマッチングアルゴリズム
- 多項式行列に対する組合せ論的緩和法の実現について(組合せ最適化)
- 分割行列の階層的分解(II) : 同値変換(離散数学)
- 分割行列の階層的分解(I) : 相似変換(離散数学)
- 正決定木によるデータ解析(組合せ最適化(1))
- 部分定義論理関数の正論理関数とHorn関数における関数分解について
- 正理論関数の部分データに基づく正決定木の構成について(組み合わせ最適化(3))
- 不完全データの論理的解析
- 不完全例題に対するプール的解析
- Extensions of Partially Defined Boolean Functions with Missing Data
- Error-Free and Best-Fit Extensions of Partially Defined Boolean Functions
- 双対制限されたハイパーグラフ:部分横断と多重横断の列挙について
- 単調線形システムにおけるすべての極小な整数解について
- ハイパーグラフの重み付き横断
- 複基多面体:台の大きさが2以下の辺ベクトルを有する多面体の構造
- フロー制約を持つソース配置問題に対する近似アルゴリズム
- 木構造動的ネットワークにおける複数個の施設配置問題(組合せ最適化(5))
- 木構造動的ネットワークにおける複数の施設への避難誘導問題(数理計画関連・数理モデル)
- 木構造の動的ネットワークにおける施設配置問題
- 木構造の動的ネットワークにおける施設配置問題(グラフ・ネットワーク(2))
- 単調双対化問題とハイパーグラフ横断列挙問題に対する新しい結果について
- ホーン理論とq-ホーン理論の極小関数従属性の推定について
- ハイパーグラフの重み付き横断
- 数値データの論理的分析(組合せ最適化(3))
- 一般化最小費用独立フロー問題とその多項式時間アルゴリズム
- L.R. Ford, Jr., & D.R. Fulkerson : Flows in Networks(20世紀の名著名論)
- 木構造ネットワークの敷設費用配分ゲーム(ゲーム理論(2))
- 劣モジュラシステムの基本構造とHitchcock型独立流(グラフ・ネットワーク(2))
- "一般性"を仮定した分割行列に関する最大最小定理とDulmage-Mendelsohn型分解(組合せ最適化)
- 独立マッチングの基本構造に関する一定理(組合せ最適化)
- 劣モジュラ関数最小化の組み合せ的強多項式時間アルゴリズム : 20年近くの未解決問題を解決
- 無向ネットワーク中のソース配置問題の強NP困難性とその近似アルゴリズム(組合せ最適化(5))
- LA-002 無向ネットワーク中のソース配置問題に対する近似アルゴリズム(A. モデル・アルゴリズム・プログラミング)
- ラミナー被覆制約を持つ単調凹関数最小化問題(グラフ・ネットワーク)
- 論理的データ解析における階層的分解構造について
- O(log n)項単調論理和標準形の効率的な双対化について
- 部分定義ブール関数のダブルホーン拡張および限定ホーン拡張
- ホーン理論と推論問題(理論計算機科学の最新動向)
- Double Horn Functions
- Double Horn Functions
- データの論理的解析とブール関数
- データの論理的解析とブール関数
- 部分定義論理関数の内核関数と外核関数
- 2-単調正論理関数の同定問題に対する単純な高速アルゴリズム
- Interior and Exterior Functions of Positive Boolean Functions
- 論理関数の内包関数と外包関数について
- 正論理関数の最大潜伏度の同定(計算量理論)
- 不完全に定義された正論理関数の最大潜伏度について
- 正論理関数の最大潜伏度について(計算機構とアルゴリズム)