====== Integer Programming and Computational Social Choice 23/24 ====== This is essentially another iteration of the [[:teaching:stfa2223|Selected Topics from Algorithms]] course, and this link contains potentially useful resources. {{tablelayout?colwidth="100px,-"&rowsHeaderSource=1&rowsVisible=100&float=left}} ^ 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 [[http://www2.imm.dtu.dk/courses/02917/Presburger1.pdf|slides]], discuss applications.| | 13. 5. | Opinion diffusion| | 20. 5. | Wrap up| ==== Resources: ==== * **{{ :teaching:stfa2223:stfa-notes.pdf |[LN]}}**: Lecture notes from last year Eventually I will post lecture notes here.