- The re-exam is now corrected. For the final results, please see this list.
- The re-exam is on February 18, 2011, 13:00-16:00 at the University of Twente, Building Carré, Room 2H. For getting around in Twente, see this link.
- The exam is now corrected. Out of the 45 participants, unfortunately 13 did not pass the exam. For the results, please see this list.
- Exam date is December 20, 2010, at 13:15-16:15 in room Wit, Ruppertbuilding, at Utrecht University
- You are allowed to use the reader as well as a printout of the lecture slides during the exam. You are not allowed to use the homework exercises neither solutions of homework exercises. Electronic devices such as smartphones or ipads are not allowed.
- I'm offering an extra session to discuss solutions of exercises on December 13, same time (13:15-15:00), same location (Aard klein). For that session, you may propose which exercises you want me to discuss.
- I prepared a list of homework exercises which I consider representative for the topics treated during the course, including an example collection of exam questions, maybe helpful for the exam preparation.
- See this list for the grades you received for the homework (up to and including set 11). This includes a standard of 5 bonus points for everybody to account for any mistakes in corrections, etc. Recall, this counts for 40% of your final grade. In case I miscounted, please email me.
- Lecture 1 on Algorithms and Spanning Trees
(pdf)
- Lecture 2 on Matroids & Shortest Paths (pdf)
- Lecture 3 on Shortest Paths & Maximum Flows (pdf)
- Lecture 4 on Flow Duality & Minimum Cost Flows (pdf).
- Lecture 5 on Minimum Cost Flows, Polyhedra and Total Unimodular Matrices (pdf).
- Lecture 6 on Total Unimodular Matrices and Matchings (pdf).
- Lecture 7 on Integer Programming (pdf). The background literature is the chapter on Integer Programming by Faigle, Kern, and Still (pdf)
- Lecture 8 on Lagrangian Relaxations, and complexity classes P, NP, and coNP (pdf).
- Lecture 9 on NP, coNP, and NP-completeness (pdf).
- Lecture 10 on NP-complete Problems (pdf).
- Lecture 11 on Primal-Dual Algorithms, PTASs and Inaproximability (pdf).
- Lecture 12 on the TSP, and a small outlook (pdf).
- Exercises 1, due Sept 27 (pdf)
- Exercises 2, due Oct 04 (pdf)
- Exercises 3, due Oct 11 (pdf)
- Exercises 4, due Oct 18 (pdf)
- Exercises 5, due Oct 25 (pdf)
- Exercises 6, due Nov 01 (pdf)
- Exercises 7, due Nov 08 (pdf)
- Exercises 8, due Nov 15 (pdf)
- Exercises 9, due Nov 22 (pdf)
- Exercises 10, due Nov 29 (pdf)
- Exercises 11, due Dec 06 (pdf)
- List of participants of Discrete Optimization, with email adresses (pdf). Please use this list to contact fellow students and form teams of 2-3 students to deliver the homework exercises.
-
If you feel unfamiliar with linear programming and LP-duality, looking at a small example may help a lot (pdf). Moreover, you find plenty of material on LP and Duality on the web, and a refreshment in Chapter 12 of the book of Vazirani (contained in the reader).
- The Ford-Fulkerson algorithm for computing a maximum flow computes an optimal solution in finite time for all networks with integer arc capacities, but may fail to find an optimum solution for irrational arc capacities. The smallest and simplest examples can be found in a paper by Uri Zwick, Theoretical Computer Science, Volume 148, Issue 1, 21 August 1995, Pages 165-170 (doi:10.1016/0304-3975(95)00022-O)
- Some lecture notes of an earlier course that I taught on approximation algorithms, also contained in the reader (pdf)
- If you want to learn more about the history of discrete optimization, read the excellent paper by Lex Schrijver (pdf)
top
Homepage Marc Uetz