日時：５月２８日（水） １５：００〜１８：００ 場所：阪大 豊中キャンパス待兼山会館 講演題目と講演者： ・ 岡崎健太郎 （京都大学大学院情報学研究科数理工学専攻 修士課程１年） 「分枝ポワソン到着をもつ単一サーバ待ち行列における呼損率の近似法」講演要旨 ・ 福永拓郎 （京都大学大学院情報学研究科数理工学専攻 修士課程１年） 「サポートベクトルマシンにおけるルールの利用」講演要旨 ・ 坂下麻里子 （大阪大学大学院基礎工学研究科システム創成専攻 修士課程１年） 「ラミナー被覆制約を持つ単調凹関数最小化問題」講演要旨 ・ 田村武幸 （京都大学大学院情報学研究科通信情報システム専攻 博士課程１年） 「Imperfectness of Data for STS-Based Physical Mapping」講演要旨 ・ 間々田聡子 （大阪大学大学院基礎工学研究科システム創成専攻 博士課程１年） 「木構造の動的ネットワーク上の施設配置問題に対する$O(n\log^2 n)$時間アルゴリズム」講演要旨
分枝ポワソン到着をもつ単一サーバ待ち行列における呼損率の近似法
岡崎健太郎（京都大学大学院情報学研究科数理工学専攻 修士課程１年）
インターネットにおけるトラヒックは, 短い時間スケールではポワソン過程と 類似のランダムな性質を示し, 比較的長い時間スケールでは強い相関を示すこ とが知られている. このような性質をもつトラヒックモデルの一つに分枝ポワ ソン過程（Branching Poisson Process, 以下BPP）がある. BPPはネットワー クの基幹網におけるパケットの到着をモデル化した到着過程と見ることもでき る. よって, BPPを入力とする単一サーバ待ち行列システムは応用上, 非常に 重要であると考えられているが, その解析は極めて困難であることが知られて いる. そこで, BPPを入力とする単一サーバ有限バッファ待ち行列システムに おける呼損率を,到着の相関構造を模擬したマルコフ変調ポワソン過程 （Markov Modulated Poisson Process, 以下MMPP）を入力とする単一サーバ有 限バッファシステムにおける呼損率を用いて近似的に求めることを考える.
サポートベクトルマシンにおけるルールの利用
福永拓郎（京都大学大学院情報学研究科数理工学専攻 修士課程１年）
サポートベクトルマシンとは, 与えられた訓練データの集合をそれぞれのデータの属するクラスに応じて分離する手法で, その学習のプロセスは簡単な二次計画問題を解くことによって行われる. データを線形な平面で分離する線形サポートベクトルマシンと, 非線形に分離する非線形サポートベクトルマシンがあり, パターン認識の分野でたいへん優れた性能を持つことで知られている. 今回はサポートベクターマシンにおける訓練データ集合の大きさを, データ集合についてのルールを生成し利用することで, なるべく本質的な情報を損なうことなく削減する手法について提案する. 訓練データ集合を削減することは, 学習や識別にかかる時間を減らすだけでなく, 記憶のための領域を減らすことにもつながり有効である.
ラミナー被覆制約を持つ単調凹関数最小化問題
坂下麻里子（大阪大学大学院基礎工学研究科システム創成専攻 修士課程１年）
Vを|V|=nである有限の集合とする．Vの部分集合族 F⊆2^Vは， 任意の集合X,Y∈Fに対して，X∩Y=Φ，X⊆Y，X⊇Yのいずれかが成立するとき， ラミナー族と呼ばれる． 本研究では，ラミナー族 F，ラミナー族上の要求関数 d，コストを表す単調凹関 数fが与えられたとき， ラミナー被覆制約と非負制約の下で，そのコスト関数を最小化する問題を考察す る． 我々は，コスト関数 fがラミナー族 FによるVの分割に基づく単調凹関数に分離 できるとき， 上記の問題がO(n^2)時間で解けることを示す．また，fがオラクルとして与えら れるときは Ω(n^2)時間必要であり，このときには我々の提案するアルゴリズムが最適であ ることを示す． さらに fが固定費付の線形関数の和として表現できる場合はO(n\log^2 n)時間ア ルゴリズムを構成する． 一般の単調凹関数 fに対しては，fがオラクルとして与えられるならばΩ (2^{n/2})時間必要であり， fが明示的に与えられる場合でもNP困難であることを示す．
Imperfectness of Data for STS-Based Physical Mapping
田村武幸（京都大学大学院情報学研究科通信情報システム専攻 博士課程１年）
In the STS-based mapping, we are requested to obtain the correct order of probes in a DNA sequence from a given set of fragments or equivalently a hybridization matrix A. It is well-known that the problem is formulated as the combinatorial problem of obtaining a permutation of A's columns so that the resulting matrix has the consecutive-one property. If the data (the hybridization matrix) is error free and includes enough information, then the above column order determines the correct order of the probes uniquely. Unfortunately this is no longer true if the data include errors, which has been one of the popular research targets in computational biology. Unfortunately, even if there is no error, ambiguities in the probe order may still remain. This obviously happens by the lack of some information of the data, but almost no further investigation was made previously. In this paper, we define a measure of such imperfectness of the data as a minimum amount of additional fragments which are needed to fix the probe order uniquely. Several polynomialtime algorithms to compute such additional fragments of minimum cost are presented.
木構造の動的ネットワーク上の施設配置問題に対する$O(n log^2 n)$時間アルゴリズム
間々田聡子（大阪大学大学院基礎工学研究科システム創成専攻 博士課程１年）
動的ネットワークとは，各枝に移動時間と容量が与えられている ネットワークである．ここで，各点に供給量がある木構造の動的ネットワークが 与えられているとき，全ての供給量をできるだけ早く送り込むことが できるような出口，点$v$を求める問題を考える． この問題は，木構造ネットワークにおける動的フローと施設配置問題を 複合したもので，木構造ネットワークにおける1-センター問題の 動的フロー版として考えることができる． 本発表では，動的に構造変更が可能な平衡2分木である区間木を用いた， $(n \log^2 n)$時間アルゴリズムについて述べる(ただし，$n$は節点数である）． (宇野，牧野，藤重との共同研究）