大学院
学内のオンライン授業の情報漏洩防止のため，URLやアカウント、教室の記載は削除しております。
最終更新日：2025年4月1日
授業計画や教室は変更となる可能性があるため、必ずUTASで最新の情報を確認して下さい。
UTASにアクセスできない方は、担当教員または部局教務へお問い合わせ下さい。
最終更新日：2025年4月1日
授業計画や教室は変更となる可能性があるため、必ずUTASで最新の情報を確認して下さい。
UTASにアクセスできない方は、担当教員または部局教務へお問い合わせ下さい。
数理構造論
Computational social choice and matroid optimization.
The first half of the course introduces various topics in computational social choice, including fair allocation of resources and voting. The second half covers discrete structures that aid in designing efficient algorithms for optimization.
時間割／共通科目コード
コース名
教員
学期
時限
4820-1008
GIF-MA6208L3
数理構造論
五十嵐 歩美
木曜2限
マイリストに追加
マイリストから削除
講義使用言語
英語
単位
2
実務経験のある教員による授業科目
NO
他学部履修
可
開講所属
情報理工学系研究科
授業計画
1. Introduction
2. Voting
3. Fair allocation of divisible goods
4. Fair allocation of indivisible goods
5. Stable matching/Cooperative games
6. Congestion games
7. Matroids
8. Matroid duality
9. Matroid polytope
10. Exchangeability graph
11. Matroid intersecion
12. Weighted matroid intersection
授業の方法
Slides will be provided for the first half of the course, while the latter half will be taught using the blackboard.
成績評価方法
Grade by assignments.
教科書
No particular textbook.
参考書
F. Brandt, V. Conitzer, U. Endriss, J. Lang, A.D. Procaccia: Handbook of Computational Social Choice, Cambridge University Press, 2016.
B. Korte and J. Vygen: Combinatorial Optimization, 5th ed., Springer-Verlag, 2010.
L. Lovasz and M. D. Plummer: Matching Theory, AMS, 2009.
A. Schrijver: Combinatorial Optimization --- Polyhedra and Efficiency, Springer- Verlag, 2003.
履修上の注意
Questions and discussions during the lecture will be welcome.
