Combinatorial Optimisation 2
SS 2019, 3 Lecture/1 Practical (MAT.482UF/MAT.483UF)E. Dragoti-Çela Department of Discrete Mathematics
Time and place of the lecture,
Time and place of the practical ,
- First lecture unit: Monday, March 4, 2019, 14:15-16:00, Seminar room AE06
- First practical unit: Thursday, March 21, 2019, 12:15-14:00, Seminar room AE06
- Contents
This course is in some sense a successor of the course Kombinatorische Optimierung 1 which is part of the bachelor program in Mathematics. Combinatorial Optimisation 2 deals in particular with NP-hard problems and focusses both on structural properties of these problems and on techniques to solve them exactly or approximately. Different approaches ans concepts such as lower bounds, heuristics, approximation algorithms, (fully) polynomial time approximation schemes, branch and bound and branch and cut approaches will be introduced and illustrated by applying them on specific problems. The goal of the course is to provide students with theoretical knowledge about basic NP-hard combinatorial optimisation problems as well as with practical appraoches to tackle them.
The main chapters and keywords are:
- Weighted matching problems in non-bipartite graphs, b-matchings, T-joins
- The travelling salesman problem: lower bounds, heuristics, approximation algorithms for the Eucleadean TSP, the TSP polytope, branch and bound approaches
- The knapsack problem: pseudopolynomial algorithms, fully polynomial approximation schemes
- The max-cut problem: the algorithm vof Goemans and Williamson
- Covering und packing problems: heuristics and approximation algorithmen
and as time permits- Network desiogn problems: the Steiner Tree Problem, a priam-dual approximation algorithm
- Literature
- W. Cook, W. Cunningham, W. Pulleyblank und A. Schrijver, Combinatorial Optimization, Wiley, 1998.
- G. Cornuejols, Combinatorial Optimization: Packing and covering, SIAM, 2001.
- D. Hochbaum (Hrsg.), Approximation Algorithms for NP-hard problems, PWS Publishing Company, 1997.
- B. Korte und J. Vygen, Combinatorial Optimiuzation: Theory and Algorithms, Springer, 2012.
- E. Lawler (Hrsg.), The traveling salesman problem: a guided tour of combinatorial optimization, Wiley, 1992.
- Assessment
The grade for the lecture will be the result of an oral examination. The dates for the oral examination will be decided upon necessity and in agreement with the students.
The grade for the practical will be based on a continuous assessment in the practical units and a written examination on June 28, 2019. The registration for the written examination should be done via TUGonline. The success of the students in the practical will be measured in terms of points which can be collected during the term and at the written examination. The maximum amount of collectable points at the written examination is 16 with a minimum of 7 points to be achieved in order to be positively graded for the practical. The maximum number of collectable points during the practical units is 16. During the practical units students can collect points by preparing and presenting their solutions of the assignmemts which will be organised in work sheets; each correctly presented solution earns the presenter 4 points. A student has to present the solutions of at least four assignments in order to be positively graded for the practical. At the beginning of each practical unit the students should report which assignments they have prepared. Among all students who have prepared a certain assignment the instructor will select the candidate to present his/her solution on the board.
There will also be a possibility to collect a maximum of four extra points, for additional presentations on the board beyond the 4 obligatory ones or for exceptionally efficient or beautiful solution ideas.
The total number of collected points is given by P= K + 8(P/A+B/(4*D))+C, where
K - points obtained at the written examination P - number of the prepared assignments B - points obtained for the presentation on the board A - overall number of assignments D - number of presentations on the board C - extra bonus points
Grade obtained for the practical according to the overall score:5 0 <= P <= 16
4 16 < P <= 20
3 20 < P <= 24
2 24 < P <=28
1 28< P
- Course materials (pdf)
(e.g. pseudo codes of algorthms or illustrating examples) will be published hier
- Work sheets (pdf)
(will be published hier, usually one week ahead of the corresponding practical unit.)
- First work sheet, to be discussed on March 25
- Second work sheet, to be discussed on April 8
- Third work sheet, to be discussed on May 6
- Fourth work sheet, to be discussed on May 20
- Fifth work sheet, to be discussed on June 3
- Sixth work sheet, to be discussed on June 17 and June 27
cela@opt.math.tu-graz.ac.at.Letzte Änderung: June 2019