Uživatelské nástroje

Nástroje pro tento web


teaching:ipcomsoc2324

Integer Programming and Computational Social Choice 23/24

This is essentially another iteration of the Selected Topics from Algorithms course, and this link contains potentially useful resources.

data what was taught [resources]
26. 2. Fixed dimension IPs, intro to iterative augmentation. [LN up to Lemma 7]
4. 3. More details for iterative augmentation. [LN up to Lemma 16]
11. 3. Norm bound, DP for case of small $m$ and $\|A\|_\infty$ [LN Lemma 16, 17]; treedepth, block-structured matrices [LN 3.4]; norm bound for $n$-fold IPs [LN Lemma 29]
18. 3. norm bounds and augmentation IP algorithms for $n$-fold and $2$-stage stochastic IPs [LN 3.5.1 and 3.6]
25. 3. Extensions: proximity theorems, coefficient reduction, strongly-poly algorithms, sensitivity [LN 4 + 5]
1. 4. Easter Monday
8. 4. Intro to voting: election, voting rule, some examples [LN 6.1-6.3]; YoungScore and DodgsonScore as fixed-dimension ILPs (double-exponential algorithm), and as few rows / $n$-fold ILPs (single-exponential algorithm). DodgsonScore is the same thing as unit cost Condorcet-Swap Bribery. Similar formulations are in [LN 8.1].
15. 4. Cancelled - KAM/IUUK spring school
22. 4. Bribery and manipulation actions as moves in societies, various voting rules, FPT algorithms.
29. 4. More voting rules; what's the deal with Young-Swap Bribery; define Campaigning Game, connect it to Presburger Arithmetic.
6. 5. Cooper's algorithm for Presburger Arithmetic slides, discuss applications.
13. 5. Opinion diffusion
20. 5. Wrap up

Resources:

  • [LN]: Lecture notes from last year

Eventually I will post lecture notes here.

teaching/ipcomsoc2324.txt · Poslední úprava: 2024/05/17 15:10 autor: Martin Koutecky