Integer Programming and Computational Social Choice - NTIN113

• Anglický název: Integer Programming and Computational Social Choice
• Zajišťuje: Informatický ústav Univerzity Karlovy (32-IUUK)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2023
• Semestr: letní
• E-Kredity: 3
• Rozsah, examinace: letní s.:2/0, Zk [HT]
• Počet míst: neomezen
• Minimální obsazenost: neomezen
• 4EU+: ne
• Virtuální mobilita / počet míst pro virtuální mobilitu: ne
• Stav předmětu: vyučován
• Jazyk výuky: angličtina
• Způsob výuky: prezenční
• Způsob výuky: prezenční
• Garant: Mgr. Martin Koutecký, Ph.D.

Anotace

Poslední úprava: RNDr. Ondřej Pangrác, Ph.D. (15.05.2023)

Integer Programming is an optimization tool rich both in theory and applications. Computational Social Choice is a field of growing relevance which considers the computational aspects of elections, fair divison, opinion dynamics, etc. In this course, we will describe algorithms for important IP and IP-related problems, and show their applications to problems from computational social choice.

Literatura

Poslední úprava: Mgr. Martin Koutecký, Ph.D. (29.01.2024)

Friedrich Eisenbrand: Integer Programming and Algorithmic Geometry of Numbers - A tutorial. 50 Years of Integer Programming 2010: 505-559

Martin Koutecký, Asaf Levin, Shmuel Onn: A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs. ICALP 2018: 85:1-85:14

Dusan Knop, Martin Koutecký, Matthias Mnich: A Unifying Framework for Manipulation Problems. AAMAS 2018: 256-264

Martin Koutecký, Nimrod Talmon: Multi-Party Campaigning. AAAI 2021: 5506-5513

Sylabus

Poslední úprava: RNDr. Ondřej Pangrác, Ph.D. (15.05.2023)

• Lenstra's algorithm (fixed-dimension IP)

• Graver basis definitions, properties, bounds, generic iterative augmentation algorithm

• n-fold and 2-stage stochastic IPs, treedepth generalization

• elections, voting rules, bribery problems

• opinion diffusion

• campaigning and Cooper's algorithm for Presburger Arithmetic