10:30-11:15 藤井海斗（東京大学）「劣モジュラ秘書問題のアルゴリズムと拡張について」
劣モジュラ秘書問題とは、ランダムな順序で一人ずつ現れる候補の中から何人かを採用し、その組合せによって決まる目的関数値を最大化する問題である。本研究では、サイズ制約の劣モジュラ秘書問題に対して新しいアルゴリズムを提案し、その競合比が既存の最良のものよりもよいことを示す。また、目的関数がk劣モジュラ関数の場合へと問題設定を拡張し、既存のアルゴリズムをサブルーチンとして用いて、さまざまな制約に対するアルゴリズムを提案する。
11:15-12:00 岩政勇仁（東京大学）「値付き制約充足問題と離散凸性：2 次値付き制約充足問題のM凸交叉による多項式時間可解なクラス」
値付き制約充足問題 (Valued Constraint Satisfaction Problem; VCSP) とは， 変数の個数が少ない関数の和で表される多変数関数の最小化問題を扱う離散最適化の枠組みである． 多くの離散最適化問題を定式化できる汎用的な枠組みだが，その汎用性ゆえ，VCSP は一般的には NP-hard である． この分野の主な目的は「どんな問題クラスが多項式時間で解けるかを解明する」ことである．
本発表では，高々 2 変数関数の和で表される関数の最小化問題 (binary VCSP) に対して， M凸交叉アルゴリズムを用いて多項式時間で最小化できる問題クラスを紹介する．
本研究は平井広志氏，室田一雄氏，Stanislav Živný氏との共同研究である．
12:00-13:00 お昼休み
13:00-13:45 松岡達也（東京大学）"Polymatroid-based capacitated packing of branchings"
全域有向木詰め込み問題を一般化した問題として，Durand de Gevigney, Nguyen, Szigeti (2013) によってマトロイド制約付き有向木詰め込み問題が定義され，解が存在するための必要十分条件と強多項式時間アルゴリズムが与えられている．本研究では，この問題の一般化であるポリマトロイド・枝容量制約付きの問題を2種類定義し，一方に対しては解が存在するための必要十分条件と強多項式時間アルゴリズムを与え，もう一方に対しては強NP完全性を示す． 本研究はZoltán Szigeti氏 (Université Grenoble Alpes, Grenoble INP, CNRS, G-SCOP) との共同研究である．
13:45-14:30 白髪丈晴（中央大学）「複数意見を持つ確率的分散投票モデルの合意時間解析」
確率的分散投票モデルは合意問題, リーダー選挙や誤り訂正などに関連するシンプルな確率的モデルであり, その合意時間に関し近年複数の研究が行われている. 完全グラフ上での解析が主だったこのモデルに対し, 本発表では, 確率行列のコンダクタンスを用いた, 一般の正則グラフ上での合意時間解析について述べる.
14:30-14:40 休憩
14:40-15:25 横井優（情報学研究所）「リスト優モジュラ彩色におけるリスト長の削減」
Galvinの枝彩色定理は「2部グラフGの各枝が，Gの最大次数以上の色をリストにもつならば，リスト枝彩色が可能である」ことを示したものである． この主張は，各枝がその端点次数によって定まるより短いリストをもつ場合でも成り立つことが，Borodin-Kostochka-Woodallによって示されている． 一方，近年Iwata-Yokoiは，Galvinの定理が，優モジュラ彩色という，より一般的な彩色問題の設定に拡張されることを示した． 本講演では，これらの結果の共通の一般化を与える．
15:25-16:10 小宮山 純平（東京大学）「確率的バンディット問題とその拡張」
博士課程の間のメインテーマであった確率的バンディット問題について解説する。確率的バンディット問題ではUCBとThompsonサンプリングと呼ばれる手法が有名だが、とくに、近年の研究の結果明らかになってきている、これらの手法がうまくいかないケースについて議論したい。
16:10-16:20 休憩
16:20-17:05 山口勇太郎（大阪大学）「クエリ可能な確率的詰め込み問題」
「詰め込み問題」とは，与えられた容量制約を満たすように要素を取捨選択し，取ると決めた要素の重みの総和を最大化する問題である． 本講演では，各要素の重みが既知の範囲で確率的に変動し，クエリすることによってその値が確定するような状況を考える． そのような状況下において，少ないクエリ回数で良い解を得るためのアルゴリズムの枠組みと，その性能評価手法を提案する．
16:50-17:40 相馬輔（東京大学）「離散凸性による劣モジュラ最大化の近似比保証」
サイズ制約での単調劣モジュラ関数最大化に対して，離散凸解析にもとづく新たな近似比評価を与える．この近似比評価は，既存の曲率による評価の一般化であることを示す．本研究はNIIの吉田悠一氏との共同研究である．