ISYE 7661: Linear Inequalities
- Instructor: Mohit Singh
- Office: Groseclose Building 410
- Contact: mohitsinghr@gmail.com
- Lecture: TU,TH 1:30PM-2:45PM
- Office Hours: TU 3:00PM-4:00PM
Course Description:
We will study the theoretical foundations of linear and integer programming with focus on algorithmic results. Topics covered will include algorithms for linear programming, polarity, diophantine approximation, lattices, basis reduction, algorithms for integer linear programming,
totally unimodularity, Total dual integrality.
Textbook:
- Theory of Linear and Integer Programming
by Alexander Schrijver, Wiley, 1998.
Additional Reading:
- Notes on Lattices by Thomas Rothvoss.
- Lectures on Polytopes, Gunter Ziegler.
Grading:
- 50% Homeworks, 20% Mid-term and 30% Final Exam.
Homeworks:
Lectures and Readings:
Lecture 1 (8/22): Complexity of Linear Equations.
Lecture 2 (8/24): Gaussian Elimination, Euclid's Algorithm.
Lecture 3 (8/29): Lattice, Hermite Normal Form.
Lecture 4 (8/31): Integral Farkas Lemma, Algorithm for HNF.
Lecture 5 (9/5): Minkowski's Theorem.
Lecture 6 (9/7): Gram Schmidt Orthogonalization, LLL algorithm.
Lecture 7 (9/19): Applications of LLL, shortest vector problem, Dirichlet's theorem.
Lecture 8 (9/21):Special Lecture: ATSP talk by Laszlo Vegh.
Lecture 9 (9/25): Fundamental theorem of Linear Inequalities.
Lecture 10 (9/26): Farkas Lemma, Linear inequalites.
Lecture 11 (9/28):