Combinatorial Optimization (Summer 2014)
|
No tutorial on Tutorial on |
We will consider combinatorial problems and concepts such as linear programming, network flows, matroids, approximation algorithms, and matchings. |
General Information
| Lecture (S. Cornelsen) | Fri 11:45 - 13:15 (F 426) Fri 13:45 - 14:30 (G 530) |
| Tutorial | Wed 13:30 - 15:00 (M 628) |
| Oral Exam | 1st date: Fri, 25th July (PZ 1006) 2nd date: Mon, 25th August (PZ 1006) |
Homework Assignments
The assignments are made available on this webpage as a PDF-file (in English) every Friday after the lecture.
The editing time for each homework is one week. It is due on the next Friday at 11:30 (AM). The assignments have to be delivered in written form either in English or German. You should submit them electronically to co_u_s14@inf.uni-konstanz.de (one PDF only!!). In the latter case, please follow the naming schema uXX_name1_name2.pdf, where XX indicates the number of the assignment. We will return the corrected and scored assignments in the tutorial. Whatever is not picked up will be placed back into the handout box.
The requirements for the admittance to the final exam are 50 percent of the total score of the assignments and regular attendance at the tutorials. In writing up your assignments, be as clear, precise, and concise as possible. Understandability will be an important factor in the scoring of the assignments. Regular attendance is considered especially for borderline cases.
Assignment 0 will be a warm-up without due-date. Please be prepared to present a solution in the first tutorial, though.
You are permitted and encouraged to work in groups of two.
| No. | Post Date | Due Date | Tutorial | Download | Material (local access only) |
|---|---|---|---|---|---|
| 00 | 25.04.2014 | --- | 02.05.2014 | Assignment00.pdf | |
| 01 | 25.04.2014 | 02.05.2014 | 07.05.2014 | Assignment01.pdf | |
| 02 | 02.05.2014 | 09.05.2014 | 14.05.2014 | Assignment02.pdf | Note: The first version contained an error mixing basic and non-basic variables. This is corrected now. |
| 03 | 09.05.2014 | 16.05.2014 | 21.05.2014 | Assignment03.pdf | |
| 04 | 16.05.2014 | 23.05.2014 | 28.05.2014 | Assignment04.pdf | |
| 05 | 23.05.2014 | 30.05.2014 | 04.06.2014 | Assignment05.pdf | |
| 06 | 30.05.2014 | 06.06.2014 | 11.06.2014 | Assignment06.pdf | |
| 07 | 06.06.2014 | 13.06.2014 | 18.06.2014 | Assignment07.pdf | |
| 08 | 13.06.2014 | 20.06.2014 | 25.06.2014 | Assignment08.pdf | |
| 09 | 20.06.2014 | 27.06.2014 | 02.07.2014 | Assignment09.pdf | |
| 10 | 27.06.2014 | 03.07.2014 | 09.07.2014 | Assignment10.pdf | Note: This assignment is due on Thursday evening. |
| 11 | 04.07.2014 | 11.07.2014 | 18.07.2014 | Assignment11.pdf | tutorial on Friday, 18th July |
| 01 | 11.07.2014 | --- | 23.07.2014 | Assignment12.pdf |
Note that some links are only locally accessible.
Lecture Notes and Supplemental Course Materials (locally accessible)
Textbooks (available at the Semesterapparat on J4)
- T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein: Introduction to Algorithms. (2nd or 3rd ed.)
- J. Kleinberg, E. Tardos: Algorithm Design
- R.K. Ahuja, T.L. Magnanti, J.B. Orlin: Network Flows. Prentice Hall, 1993. Cook, Cunningham, Pulleyblank, Schrijver: Combinatorial Optimization
- D.Bertsimas, J. N. Tsitsiklis: Introduction to Linear Optimization