■第19回研究会(2006年2月18日(土)14:00--18:00 東京大学 工学部6号館)の講演概要
 
14:00--15:50『スポーツのスケジューリング問題に対する効率の良い解法』筑波大学 鈴鹿 順美 氏
スポーツのスケジューリング問題と呼ばれる,総当たり戦形式で行われるスポーツの競技会の最適な試合日程の作成問題の中の,会場割当て問題について扱う.会場割当て問題とは,与えられた対戦組合せと参加チームの本拠地間の距離データに対して,総移動距離を最小にするホーム・アウェイの割当てを求める問題である.会場割当て問題に対して,Bertsimas--Teo--Vhora(1999)の線形緩和に基づく近似解法と,Goemans--Williamson(1995)の半正定値緩和に基づく近似解法を基に二つのアルゴリズムを提案し,計算機実験を行った.計算機実験の結果から,これらのアルゴリズムによって会場割当て問題を高速に解くことができ,非常に精度の高い近似解が得られていることが示された.なお,本研究は,宮代隆平(東京農工大学),吉瀬章子(筑波大学),松井知己(東京大学)との共同研究である.
 
16:10--18:00『ネットワークに最大流が存在することの証明とよもやま話』広島大学 榎本 彦衛 氏
「最大流-最小カット定理」には、最大流が存在することも implicit に主張している。しかし、ネットワークを扱った本で、最大流が存在することをちゃんと証明しているものは少なく、ある流れfが最大流であるための必要十分条件は増大道が存在しないことであり、そのときfの流量と容量が一致するカットが存在することを証明しているだけ、ということが多い。本当は最大流が存在することを証明しないといけないが省略する、と断っている良心的な本もたまにあるが、最大流が存在することの証明が必要だということを認識していないと思われることが結構多い。「有界な実数列には収束する部分列が存在する」ということを使えば、最大流が存在することの証明は難しいことではないが、この証明方法は、「容量が有理数のとき、すべての辺の流量が有理数であるような最大流が存在する」ということの証明には使えない。本講演では、実数の完備性を使わず、もっと一般的な状況を扱えて高校生にも理解できる証明を紹介する。それだけでは時間があまると思うので、あとはよもやま話で時間をつぶしたいと思う。
 
Seminars on Algorithms in Operations Research
ホーム - SAORについて - 会場案内 - 全日程 - リンク
(c) 2003-2004 SAOR All rights reserved.