Computational Complexity in Optimization (MA 5222)

### lecture

Prof. Dr. Peter Gritzmann, Dr. Steffen Borgwardt |

News | Dates of lectures/exercise classes | Office Hours | Lecture notes | Problem sheets | Exam | Literature | FAQ |

# News

- July 24th: The results of the exam are online. A possibility to review your exam, as announced before, is tomorrow
**July 25th, 11:00-12:00**in room**MI 02.06.020**. - July 11th: A final announcement for the closed-book exam on July 23rd: Answers are accepted in both German and English.
- June 26th: On
**July 7th**, the lecture slot is taken by the last exercise class (**instead of**Wednesday!!). The class serves as preparation for the written exam. - May 20th: The fourth exercise class is postponed by exactly one week and 15 minutes. It is on
**June 4th, 16:15-17:45**. The corresponding sheet is distributed in the exercise class itself. All other classes are scheduled normally, in particular, the fifth class is on June 11th. - Apr, 28nd: Based on student attendance, the exercise classes are now in a two-week rhythm with one slot. This week, April 30th, there will be a class.
- Apr, 22nd: As announced in the lecture, there is no exercise class tomorrow, April 23rd.
- Apr, 15th: By request, the exercise classes already start at
**16:00**! - Apr, 10th: Details on the exercise classes are online. The first classes of our two exercise groups are on
**April 16th**and**April 23rd**. There will be a two-week rhythm for these classes! - Apr, 8th: Literature is online. Details on room and date of the exercise classes are TBA.
- Apr, 3rd: The homepage is online.

# Exam

# Dates of lectures/exercise classes

Type | Day | Time | Room | Teacher/Tutor | Language | Comment |
---|---|---|---|---|---|---|

Lecture | Monday | 12:15-14:00 | MI HS 3 | Gritzmann | english | |

Exercises | Wednesday | 16:00-17:30 | MW 1701 | Borgwardt | english | two-week rhythm, starting April 16th |

# Office hours

Person | Office hours (during semester) |
---|---|

Peter Gritzmann | Friday, 16-17 h (on all Fridays when there are lectures) or by appointment |

Steffen Borgwardt | by appointment |

# Lecture notes

- lecture 1
- lecture 2
- lecture 3
- lecture 4
- lecture 5
- lecture 6
- lecture 7
- lecture 8
- lecture 9
- lecture 10

# Problem sheets

- exercises 1
- solutions 1
- exercises 2
- solutions 2
- exercises 3
- solutions 3
- exercises 4
- solutions 4
- exercises 5
- solutions 5
- exercises 6
- solutions 6

# Literature

- P. Gritzmann.
**Grundlagen der Mathematischen Optimierung**. Springer Spektrum, 2013 - J.E. Hopcroft, R. Motwani and J.D. Ullman.
**Introduction to Automata Theory, Languages, and Computation**. Addison-Wesley, 3rd ed. 2006 - J. Kleinberg, E. Tardos.
**Algorithm Design**. Addison-Wesley, 2006 - M.R. Garey, D.S. Johnson.
**Computers and Intractability: A Guide to the Theory of NP-Completeness**. Freeman, 1979 - I. Wegener.
**Komplexitätstheorie**. Springer, 2003