第１３回研究会（２００８年１１月１日（土） １４時 〜）講演概要
会場： 秋葉原ダイビル １２階 公立大学法人首都大学東京 秋葉原サテライトキャンパス
詳細はこちら
講演者：
来嶋 秀治 氏 （京都大学 数理解析研究所）
タイトル：
一般化メディアン安定結婚問題に対する乱択近似アルゴリズム
概要： （一般化）メディアン安定結婚は，問題構造から誘導さ れる公平な安定マッチングとして，Teo-Sethuraman(1998) によって提案された．本講演では一般化メディアン安定 結婚問題の解法について議論する．具体的には，問題の #P困難性について述べ，素朴な乱択アルゴリズムにより， 精度保証付きの近似解が得られることを述べる．以上の 議論においては，根本(2000), Cheng(2008)によって独立 に発見された特徴づけに基づいて，半順序集合上のレベ ルイデアル問題に変形して議論する． 本研究は，文教大学の根本俊男教授との共同研究である．
講演者：
小野 廣隆 氏 （九州大学）
タイトル：
木のL(2,1)-ラベリング に対する高速アルゴリズム
概要： グラフのk-L(2,1)-ラベリングとは，頂点への 1から k までの整数値の 割り当てであり，隣接頂点間では少なくとも 2，距離2の頂点間では 少なくとも 1 の差があるもののことを言う．L(2,1)-ラベリング問題とは， グラフに対するk-L(2,1)ラベリングの中で最小の k を求めるものである． この問題は，木幅が2のグラフに対してでもNP困難であることが知られている． 一方，多項式時間アルゴリズムは，路や閉路，木といった限られたクラスにしか 知られておらず，木に対してもこれまではO(Δ^{4.5}n)時間の アルゴリズムしか知られていなかった（ただし，Δはグラフの最大次数）． 本発表では，発表者らが開発した木に対するL(2,1)ラベリング問題を解く， O(n^{1.75})時間アルゴリズム，O(n log^2 n)時間アルゴリズム，O(n)時間 アルゴリズムを紹介する．
ホーム
Copyright, S@CO All rights reserved, 2006-2008.
