Combinatorial Optimization 2 (MAT.482/MAT.483)

Summer Term 2021

Bettina Klinz

  Scheduled dates

  Office hours

  Contents of the course

  Literature

  Exercise sheets

  Exams

Scheduled dates

Office Hours

Contents and Goal of the Course

• Short introduction to approximation algorithms (notions: constant factor approximation, PTAS, FPTAS)
• Covering and packing problems: bin packing, knapsack problem, heuristics, approximation algorithms+schemes, dynamic programming.
• Travelling salesman problem (TSP): lower bounds, heuristics, approximation algorithms, branch&bound, TSP polytope
• Quadratic assignment problem (QAP): lower bounds, heuristics
• Weighted nonbipartite matching problems, weighted T-joins
• Matroid intersection (if time permits, not likely to happen)

Literature

General text books and monographs

• W.J. Cook, W.H. Cunningham, W.H. Pulleyblank, A. Schrijver, Combinatorial Optimization,
  Wiley-Interscience, John Wiley & Sons, New York, 1998, 355 pages, ISBN 0-471-55894-X.
  (Easily readable, but yet modern text book. Covers less topics than the book by Korte and Vygen - is a good reference for matching algorithms.)

• B. Korte, J. Vygen, Combinatorial Optimization,
  Springer Verlag, Berlin, Heidelberg, New York, 2nd edition, 2002, 530 pages, ISBN 3-540-43154-3.
  Very extensive book. For the German version an e-book version is available within the TU Graz network.

• G.L. Nemhauser, L.A. Wolsey, Integer and Combinatorial Optimization,
  Wiley-Interscience, John Wiley & Sons, New York, 1988, 763 pages, ISBN 0-471-35943-2.
  (Parts of the book are outdated. The book provides a very comprehensive treatment of integer programming well beyond the scope of this course.)

• A. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency,
  Springer, Berlin, Heidelberg, New York, 2003, 3 volumes (Volume A: 648 pages, Volume B: 570 pages, Volume C: 664 pages), ISBN: 3-540-44389-4. (Very comprehensive monograph on combinatorial optimization; special focus on polyhedral results and efficient algorithms, over 400 references, almost 2000 pages!)

Literature about special topics (QAP, TSP, approximation)

• R.E. Burkard, M. Dell'Amico and S. Martello, Assignment Problems,
  SIAM, Philadelphia, 2012 (revised reprint), 393 pages, ISBN 978-1-61197-222-1.
  Provides an extensive treatment of various types of assignment problems (linear, quadratic, multi-dimensional).

• E. Cela, The Quadratic Assignment Problem,
  Springe-Science+Business Media Dortrecht (originally published by Kluwer Adademic Publishers), 1998, 287 pages, ISBN 978-1-4419-4786-4.
  Monograph on the quadratic assignment problem.

• H. Kellerer, U. Pferschy, D. Pisinger, Knapsack Problems,
  Springer, 2004, 548 pages, ISBN 978-3-540-40286-2.
Monograph on knapsack problems and variants.

• E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, D.B. Shmoys (eds), The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization,
  Wiley, 1985, 476 pages, ISBN 978-0-471-90413-7.
  Provides an in-depth treatment of the TSP - the archetypical hard problem in combinatorial optimization.

• D.S. Hochbaum (ed)., Approximation Algorithms for NP-hard Problems,
  PWS Publishing Company, Boston, MA, 1997, 596 pages, ISBN 0-534-94968-1.
  Provides a thorough study of approximation algorithms as a tool for coping with intractable problems.

• D.P. Williamson and D.B. Shmoys, The Design of Approximation Algorithms,
  Cambridge University Press, 2011, 518 pages, 978-0-521-19527-0.
  Very recommendable and price-winning textbook for graduate-level courses on approximation algorithms. Can also serve as a good reference for researchers in the area and is much more recent than the Hochbaum book.
  A pdf file of the book for personal usage can be downloaded from here.

Practical

General comments

Exercise Sheets

Exam/Grading information

Grading of the Lecture

Grading of the Practical