■第1回研究会(2003年4月19日(土)14:00--18:00 東京大学 工学部6号館 3階セミナー室A&D)の講演概要
 
14:00--15:10『小選挙区区割画定問題に対する数理的アプローチ』文教大学 根本俊男 氏
日本の衆議院議員選挙は小選挙区比例代表並立制により実施されている.その中の小選挙区制の実施に必要な300小選挙区の「良い」区割を見つける問題を「小選挙区区割問題」とよぶ.区割は都道府県内でしか認められないので,議員定数を各都道府県にどう配分するかの「定数配分問題」と,配分された議員定数を基に小選挙区をどう画定するかの「区割画定問題」の2つが互いに絡み合う問題として小選挙区区割問題を捉えなくてはならない.
前者の定数配分問題に関してはOR分野や公共政策分野等で様々な角度から議論され,数理的にも多くの知見が提供されてきたが,その一方で,なぜか区割画定問題に関しての取り組みはあまり見受けられない.
そこで本発表では,区割画定問題の観点から,小選挙区の「良い」区割を数理的に見つけていく取り組みについて紹介したい.
 
15:25--16:35『グラフアルゴリズムの応用 - メモリ不良救済と乗り換え経路探索 -』(株)東芝 半田恵一 氏
グラフアルゴリズムの応用事例を2つ紹介する。1つは、DM分解をメモリデバイスの不良救済問題に応用したものである。不良救済問題とは、メモリ上の不良ビットの集まりを所与の複数の代替ライン(スペア)に置き換えることによって救済するというものであり、NP完全であることが知られている。本講演では、不良のスペアも容易に活用できるモデル化や、スペアの細分化にも対応できるヒューリスティックな解法を紹介する。もう1つは、第1-K最短パスを求めるアルゴリズムを、電車の乗り換え案内(駅前探険倶楽部)における経路探索問題に応用したものである。有効な代替経路を求めるために工夫した点を幾つか紹介する。
 
16:50--18:00『MAX 2-SAT と MAX DICUT に対する新たな近似解法』東京大学 松浦史郎 氏
MAX 2-SAT 問題と MAX DICUT 問題に対し, Goemans と Williamsonによる半正定値計画緩和を用いた確率的近似解法を元にした新たな近似解法を解説する. この解法では, 確率的な操作を一様分布ではなく特殊な分布を用いて行なう事によって近似比を向上をさせている. また, この解法の脱ランダム化(derandomization)についても解説し, 得られる決定的解法の近似比が本質的には確率分布に依存しない事を示す.
 
Seminars on Algorithms in Operations Research
ホーム - SAORについて - 会場案内 - 全日程 - リンク
(c) 2003-2004 SAOR All rights reserved.