Combinatorial Optimization 1 (MAT.321/MAT.322)

Winter Term 2015/16

Bettina Klinz

  Scheduled dates

  Office hours

  Contents of the course

  Literature

  On-line materials

  Exercise sheets

  Exams

Scheduled dates

Office Hours

Contents and Goal of the Course

• Introductory examples of combinatorial optimization; motivation
• Short and informal introduction into the notions from complexity theory needed in the course
• Minimum spanning tree problems and related problems
• Matroids and the greedy algorithm
• Optimal arborescences and branchings
• Shortest path problems
• Maximum flow problems
• Minimum cost flow problems
• Matching problems
• Short introduction into key concepts in integer optimization (integer hull of a polyhedron, total unimodularity, total dual integrality, and cutting planes if time permits)

Literature

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

• 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!)

• R.K. Ahuja, T.L. Magnanti, J.B. Orlin, Network Flows: Theory, Algorithms, and Applications,
  Prentice Hall, Englewood-Cliffs, New Jersey, 1993, 864 pages, ISBN 0-13-617549-X.
  (This book provides an extensive and very recommendable treatment of the area of network flow problems (including also topics like spanning trees and shortest paths), a subarea of combinatorial optimization.

• E.L. Lawler, Combinatorial Optimization: Networks and Matroids,
  Dover Publications, 2001, 374 pages, ISBN 0-486-41453-1.
  (Republication of the original edition that was published by Holt, Rhinehart amd Winston, New York in 1976)

• C. Papadimitriou, K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity,
  Dover Publications, Inc, 1988, 496 pages, ISBN 0-486-40258-4.
  (Corrected, unabridged republication of the original edition that was published in 1982 by Prentice Hall, Englewood Cliffs, New Jersey
  and has been out of print for several years.)

Bibliographies

• M.O'hEigeartaigh, J.K. Lenstra, A.H.G. Rinnooy Kan (eds.), Combinatorial Optimization: Annotated Bibliographies,
  Wiley, New York, 1985.

• M. Dell'Amico, F. Maffioli, S. Martello (eds), Annotated Bibliographies in Combinatorial Optimization,
  Wiley-Interscience, John Wiley & Sons, New York, 1997, 495 pages, ISBN 0-471-96574-X.
  (covers roughly the period 1985-1997).

On-Line Materials

• Link list "Combinatorial optimization" (under construction).

Practical

General comments

Exercise Sheets