–
2021-07-30
日時：2021年7月30日（金）14時〜18時
会場：Zoom によるオンライン開催
参加方法：開催日前に接続先情報をお知らせしますので、以下のフォームから参加登録をお願い致します。
参加登録フォーム：https://forms.gle/DkpXFk79zEistvd67
講演 1
講演者：武流野・F・ロウレンソ 氏（統計数理研究所）
講演題目：錐最適化におけるエラーバウンド：一から最近の結果まで
講演概要：
本発表で錐最適化におけるエラーバウンドとその背景を紹介する．
特に，どうしてエラーバウンドが必要か，どのようにエラーバウンドが使われいてるかなど，一から説明する．
モチベーションをしっかり説明してから，恭順錐や面縮小法とエラーバウンドの繋がりを紹介し，エラーバウンドの計算方法を簡単に述べる．
皆様のご興味に応じて，他の最近の結果も紹介する．例：恭順錐の幾何学，恭順錐ではない錐のエラーバウンドを求める方法，エラーバウンドとアルゴリズム解析の関係など．
関連するarxivの論文：1712.06221, 2008.12968, 2010.16391, 2011.07745, 2102.06359．
講演 2
講演者：河瀬康志 氏（東京大学）
講演題目：不可分財の確率的公平割当
講演概要：
限られた資源や財を公平かつ効率的に割り当てるという問題は，基本的かつ重要な問題である． 近年，アルゴリズム的ゲーム理論の分野では，不可分な財の「よい」割当を求める手法について関心を集めている． 本発表では，期待効用の最小値を最大化する確率的割当を求める問題を扱い，各エージェントの効用関数が加法性，粗代替性，劣モジュラ性を満たす場合それぞれについて，多項式時間（近似）アルゴリズムを与える． また，無羨望制約を追加で満たす必要がある場合について，計算可能性を議論する．
参加費用：無料
参加資格：自由 (会員/非会員不問)。学生の方のご参加も歓迎いたします。
問い合わせ：幹事 伊藤勝（ito.m@math.cst.nihon-u.ac.jp）
研究部会 最適化手法とアルゴリズム (SOMA)
URL: http://trout.math.cst.nihon-u.ac.jp/~ito.m/soma/index.html