Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Integer Optimization: Theory and Applications
This lecture covers the fundamentals of integer optimization, including integer programming, dynamic programming, approximation algorithms, and set-cover problems. The instructor discusses the complexity of integer programming, the linear programming relaxation, branch & bound, and the knapsack problem. The lecture also explores topics such as Steinitz Lemma, GCD, Euclidean Algorithm, lattices, Minkowski's Theorem, and transference bounds. Additionally, the lecture delves into the application of integer programming in fixed dimension and algorithms for the Shortest Vector Problem (SVP).