Toto je starší verze dokumentu!

Integer Programming and Computational Social Choice 24/25

data	what was taught [resources]
17. 2.	Fixed dimension IPs, birds-eye overview of iterative augmentation. [LN 1-2]
24. 2.	Iterative augmentation: Graver basis, positive sum property [LN 3, until Prop 6]
3. 3.	Iterative augmentation: convergence, (AugIP), feasibility [LN 3, until end of 3.1]
10. 3.	Steinitz Lemma, basic $g_1(A)$ bound, sketch of extension to $n$-folds. [LN 3, until Thm 17]
17. 3.	Basic (AugIP) DP, DP for $n$-folds [LN 3, until Lemma 19]
24. 3.	Klein's lemma and $2$-stage norm bound, $2$-stage branching [LN 3.5]
31. 3.	Extensions: proximity theorems, coefficient reduction, strongly-poly algorithms, sensitivity [LN 4 + 5]
7. 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].
14. 4.	Bribery and manipulation actions as moves in societies, various voting rules, FPT algorithms.
21. 4.	Cancelled - Easter Monday
28. 4.	Presburger Arithmetic, Cooper's Algorithm, and Multi-party Campaigning
5. 5.	Opinion Diffusion

[LN]: Lecture notes (hopefully continuously updated 😅). autogenerated PDF (login required)

Eventually (😅😅😅) I will post lecture notes here.