| 講演名 | 2002/11/22 ヒッチコック型輸送問題に対する途中棄却を含む段階的解法 池田 隆之, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | ヒッチコック型輸送問題の費用と閾値の比較を行う判定問題のアルゴリズムを提案する.最適解を求めるよりも少ない計算時間で求めることが可能な下界を求め,閾値との比較を段階的に行う.比較の結果,下界が閾値よりも大きいことがわかればその段階で棄却する.費用と閾値との間に大きな差がある場合にはより早い段階で棄却されるため計算時間も短くなる.一般のヒッチコック型輸送問題では下界を求めることが困難であることから,本論文ではユークリッド空間上の点集合を考え,2点間の単位流量当りの費用がその距離で与えられるとする.入力されたグラフを縮約し,問題の規模を小さくする.縮約されたグラフにおけるヒッチコック型輸送問題の最小費用が縮約を行う前のグラフにおける最小費用の下界を与えることを示す.また,最小費用と閾値の差が小さく,縮約されたグラフでは判定を行えない場合に,最初に与えられた問題を解くことになっても計算量が増加しないことを示す. |
| 抄録(英) | We propose an algorithm for comparing the cost of the Hitchcock type transportation problem with a given threshold. Since we can calculate a lower bound in less time than that for finding an optimal solution, our algorithm compares the lower bound with the threshold gradually. If it turns out that a lower bound is greater than the threshold, it will reject it in this stage. Since it is rejected in an earlier stage when there is a big difference between the lower bound and the threshold, computation time also becomes shorter. In the general Hitchcock type transportation problem, it is difficult to establish a lower bound. Therefore, in this paper, we consider a point set on the Euclidean space and suppose that the cost per unit flow for two points is given by their distance. An input graph is contracted, which scales down the problem. We show that the cost of the Hitchcock type transportation problem in the contracted graph is equal to the lower bound of the cost in the graph before contracting. |
| キーワード(和) | 最小費用流問題 / ネットワーク計画問題 |
| キーワード(英) | minimum cost flow / network programing problem |
| 資料番号 | COMP2002-48 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2002/11/22(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | ヒッチコック型輸送問題に対する途中棄却を含む段階的解法 |
| サブタイトル（和） | |
| タイトル（英） | Stepwise Algorithm with Abort for Hitchcock Type Transportation Problem |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 最小費用流問題 / minimum cost flow |
| キーワード(2)（和/英） | ネットワーク計画問題 / network programing problem |
| 第 1 著者 氏名（和/英） | 池田 隆之 / Takayuki IKEDA |
| 第 1 著者 所属（和/英） | 北陸先端科学技術大学院 大学情報科学研究科 School of Information Science Japan Advanced Institute of Science and Technology |
| 発表年月日 | 2002/11/22 |
| 資料番号 | COMP2002-48 |
| 巻番号（vol） | vol.102 |
| 号番号（no） | 490 |
| ページ範囲 | pp.- |
| ページ数 | 5 |
| 発行日 | |