■第7回研究会 (2004年3月6日(土)14:00--18:00 東京大学 工学部6号館) の講演概要
 
14:00--15:50 『ブレーク数最適化問題に対するアプローチ』 東京大学 宮代隆平
ブレーク数最適化問題とは、スポーツスケジューリングと呼ばれる分野において扱われるスケジューリング問題の一つである。この問題は、ブレーク数の最大化と最小化の両方に実用的な意味があり、移動距離の最小化を目指す場合には前者の、公平性を重視するスケジューリングを行う際には後者の最適化が行われる。これらは両方ともNP-困難と予想されており、これまでに分枝限定法をベースにした解法がいくつか提案されてきたが、二つの問題に対する統一的な枠組みは与えられていなかった。ごく最近に発表者のグループは、与えられた入力に対してブレーク数が最大の解から最小の解を構成する、また逆を行うアルゴリズムを開発した。さらに、Elf・Juenger・Rinaldi (2003)により提案されていた、「(ブレーク数最小化問題の)入力がある条件を満たす場合には多項式時間で求解可能である」という予想を肯定的に解決した。今回の発表では、これらの結果を紹介する。
 
16:10--18:00 『ゲノムの類似部分発見問題』 国立情報学研究所 宇野毅明 氏
近年、ヒトゲノムの解読が終了し、人の遺伝情報はデータとして手に入れることができるようになった。しかし、このゲノムデータは、いわば鉱石のようなもので、そのままでは意味の分からないデータであり、遺伝子や種の進化の痕跡などの有用な情報を取り出すためには、ゲノムデータを解析し、情報を取り出す作業をする必要がある。その解析で解かれる問題の1つに「類似する部分を見つける」というものがある。
進化によりゲノムが変化する場合、部分的な変化のほかに、ある部分が他に移動する、あるいは向きが変わる、という変化がおきる。そのため、ゲノム全体の類似度を計算するだけでは不十分であり、どことどこが似ているのか、という情報が必要になる。また、遺伝病の診断などでは、なるべく固有な部分列、つまりは類似する部分列が存在しないような部分列を用いる必要がある。
本発表では、この問題に対する既存研究と、新しい高速なアルゴリズムの解説を行う。
 
Seminars on Algorithms in Operations Research
ホーム - SAORについて - 会場案内 - 全日程 - リンク
(c) 2003-2004 SAOR All rights reserved.