Combinatorial Optimization, MA4502 (in English)
|Dozent:||Prof. Dr. Anusch Taraz|
|Übungsleitung:||Dipl.-Math. Felix Schmiedl|
|News||Dates of lectures/exercise classes and office hours||Lecture notes|
- Oct 9: The grades for the exam haven been published on TUMOnline.
- Oct 7: The exam inspection is scheduled for Monday, October 14, at 10:00 in room MI 02.06.020. Please bring a photo ID! More details can be found below in the exam section.
- Aug 7: The grades for the exam haven been published on TUMOnline. The exam inspection is scheduled for Wednesday, August 14, at 10:00 in room MI 02.06.020. Please bring a photo ID! More details can be found below in the exam section.
- Jul 16: There will be an extra tutorial on Thursday, Jul 25 at 10:00 hours in room 02.04.011, where you can ask questions regarding the material covered in the lecture and exercise lasses.
- Jul 16: The exams from last semester are now online.
- May 29: The time of the exam has been changed to 11:00 hours.
- May 15: The date of the exam has been fixed.
- Apr 18: The room for exercise class 2 has been changed to MI 02.08.020!
- Apr 17: Added Lecture notes for required bachelor courses.
- Apr 16: Starting April 23rd, the lecture will begin at 16:00 hours.
Dates of lectures/exercise classes and office hours
|lecture||Tuesday||16:00 - 17:30||MI 00.07.014|
|exercise class 1||Thursday||16:00 - 17:30||MI 03.10.011||Apr 18, May 2, May 16, Jun 6, Jun 13, Jun 27, Jul 11|
|exercise class 2||Friday||12:15 - 13:45||MI 02.08.020||Apr 19, May 3, May 17, Jun 7, Jun 14, Jun 28, Jul 12|
|Person||Office hours (during semester)|
|Anusch Taraz||by appointment|
|Felix Schmiedl||by appointment|
- All topics covered in the lecture and the exercise classes are relevant for the exam.
- Registration via TUMOnline is mandatory for participation for the exam (registration for the lecture and/or the exercise classes is not sufficient!)
- The dates and times posted below are preliminary and subject to change.
Dates and Times
|Tue, July 30, 2013||11:00||Interims HS 2||until June 30, 2013 via TUMOnline||first attempt|
|Wed, Oct 2, 2013||12:00||MI HS 2||Sep 2 - Sep 16, 2013 via TUMOnline||second (and last) attempt|
- An inspection of the graded exams is possible on October 14, 10:00 hours in room MI 02.06.020.
- Please remember to bring your photo ID to the inspection!
- You may authorize a fellow student of your choice to inspect your exam for you. Please write a certificate of authority stating both your full name and the full name of the authorized person and sign the certificate. The authorized person needs to present a photo ID!
- You may take photos of your (and only your) exams (if you bring a camera). Authorized persons (see previous point) may also take photos of any exam they are authorized to inspect. Please be advised that xeroxing or scanning the exams will not be possible.
- A suggested solution will be available during the inspection.
Lecture notesFor a complete set of lecture notes similar to the topics covered in this lecture see the notes of WS 2010/2011 by Prof. Raymond Hemmecke: CombOpt 2010 or of WS 2012/2013 by Prof. Anusch Taraz: CombOpt 2012.
|Apr 16, 2013||1. Approximation algorithms (TSP hardness)|
|Apr 23, 2013||1. Approximation algorithms (heuristics for the TSP)|
|Apr 30, 2013||1. Approximation algorithms (Knapsack: dyn programming and FPTAS)|
|May 07, 2013||2. Methods to strengthen an ILP-formulation (Polyhedral geometry revisited)|
|May 14, 2013||2. Methods to strengthen an ILP-formulation|
|July 02, 2013||6.1 Benders decomposition|
|July 09, 2013||6.2 Lagrange relaxation|
|July 16, 2013||6.2 Subgradient plus Branch and Bound|
|Apr 18/19||exercise sheet 1||sheet01.pdf||sheet01-sol.pdf|
|May 2/3||exercise sheet 2||sheet02.pdf||sheet02-sol.pdf|
|May 16/17||exercise sheet 3||sheet03.pdf||sheet03-sol.pdf|
|Jun 6/7||exercise sheet 4||sheet04.pdf||sheet04-sol.pdf|
|Jun 13/14||exercise sheet 5||sheet05.pdf||sheet05-sol.pdf|
|Jun 27/28||exercise sheet 6||sheet06.pdf||sheet06-sol.pdf|
|Jul 11/12||exercise sheet 7||sheet07.pdf||sheet07-sol.pdf|
|SS 13 first||exam13-1.pdf||exam13-1-sol.pdf|
- Cook, Cunningham, Pulleyblank, Schrijver, Combinatorial Optimization, Wiley 1998
- Korte, Vygen, Combinatorial Optimization: Theory and Algorithms, Springer 2002
- Nemhauser, Wolsey: Integer and Combinatorial Optimization 1999
- Papadimitriou, Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Dover 1998
- Wolsey: Integer Programming, 1998
FAQWill the tutorials be in English or in German?
There will be at least one English tutorial. The total number of tutorial classes and availability of a German tutorial are subject to participation and will be discussed during the first week of lectures. However, the exercise sheets will be available in English only. Will the exam be in English or in German?
There will be a written exam with questions in English. Answers will be accepted in both English and German (provided the answers are correct, of course).