■第6回研究会(2004年1月24日(土)14:00--18:00 東京大学 工学部6号館)の講演概要
 
14:00--15:50『M凸劣モジュラ流に対する容量スケーリング法』東京工業大学 森口聡子 氏
M凸劣モジュラ流問題(室田, 1999)は, フローの境界に対する費用が M凸関数で与えられた最小費用流問題で, 多項式時間アルゴリズムが 知られている組合せ最適化問題の中で最も一般的な枠組みの一つとして 知られている. 本発表では, 現時点で最も効率的にこの問題を解く, 岩田・森口・室田による新しい容量スケーリング法を紹介する.
このアルゴリズムは, Fleischer・岩田・McCormickによる最小費用 劣モジュラ流問題に対する緩和枝を用いた手法を拡張している. 更に, 最大劣モジュラ流問題を繰返し解くことでポテンシャルを 更新するという新しい手続きを導入している.
 
16:10--18:00『流れの中のボロノイ図』東京大学 西田徹志 氏
ボロノイ図とは,平面上にいくつかの母点が与えられたときに,ある母点までの ユークリッド距離が他の母点までの距離よりも短くなるような点を集めてできる領 域に,平面を分割した図形をいう.そして,このボロノイ図はその領域の境界辺を 解析的に求めることで得られる.ボロノイ図は様々な変種が考えられているが,そ のほとんどがユークリッド距離を他の距離に置き換え,そして境界を解析的に求め ることで得られる.
しかし,境界を解析的に求めることができないボロノイ図がいくつか存在する. その内のひとつが,ボート航行距離ボロノイ図である.このボロノイ図は,流れの ある水面上を航行するボートの振舞いをモデル化することによってボート航行距離 を定義し,その距離を用いて作られる図である.
我々は,このボロノイ図を計算する問題を,偏微分方程式の境界値問題に定式化 し,その境界値問題を解く数値計算法を提案した.その方法はeikonal方程式に対 して提案されたfast marching法を改良したものである.今回は,これらの研究結 果について発表する.
 
Seminars on Algorithms in Operations Research
ホーム - SAORについて - 会場案内 - 全日程 - リンク
(c) 2003-2004 SAOR All rights reserved.