第8回研究会 (2020/12/2)

以下の通り，第8回研究会を開催いたしました．

日時: 2020年12月2日 (水) 15:00～17:30 14:30～18:00

場所: Zoom によるオンライン開催

参加者: 34 名

[講演1]

講演者: 小林 靖明 氏（京都大学 大学院情報学研究科）

題目: 単調な性質を持つサイズ制約付き極小解の近似列挙アルゴリズム

概要: グラフの頂点カバーや行列の列ベクトルの線形従属性などは，包含関係に関して単調な性質である．このような性質を満たす極小な集合の列挙問題は列挙アルゴリズムの分野において中心的なテーマのひとつであり，これらに対する多項式遅延アルゴリズムを開発することがひとつの目標となっている．しかしながら，列挙アルゴリズムがすべての解を重複なくかつ漏れなく出力するという性質上，アルゴリズム全体の実行時間は解の総数に本質的に依存する．解の総数を合理的に減らすためのひとつのアイデアは，出力する解の大きさに制限を加えることであるが，頂点カバーなどの問題に対しては解をひとつ求めることですらNP困難となってしまう．そこで本研究では列挙アルゴリズムに「近似」の概念を導入し，様々な単調な性質を持つサイズ制約付き極小解の列挙問題に対して効率的な近似列挙アルゴリズム与える．本発表においては，列挙アルゴリズムに関する近年の進展を紹介しつつ，本研究の成果について述べる．本研究は栗田和宏氏，和佐州洋氏との共同研究である．

[講演2]

講演者: 河村 彰星 氏（京都大学 数理解析研究所）

題目: 輪番スケジューリングと密度限界

概要: 整数全体を何色かに塗り分けたい。但し各色について、それを塗る間隔の下界（ないし上界）が定まっている。 塗り分けが可能なのは如何なるときであろうか。これは「設備の保守」「警備」「献立」「広告の表示」などのスケジューリングに現れる問題といえる。 必要条件、十分条件や判定の計算量について考える。