University of Konstanz
Algorithmics Group
Prof. Dr. Ulrik Brandes

Combinatorial Optimization (Summer 2014)


No tutorial on
July 16

Tutorial on
July 18, 1:30 p.m.
in G 530

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)

Please register for this course in the StudIS and LSF.

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 (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)

Further Information