Class at Faculty of Mathematics and Physics |
NTIN113
Syllabus
- 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
Annotation
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.