LS 2

Home
Teaching (German)
Service
Travel
Staff
Contact
Private

External Links

Universität Dortmund
Computer Science Faculty
Collab. Research Center 531
Collab. Research Center 475
Research Cluster 1126
Student Advisory

Spezialvorlesung

Optimization

Wintersemester 2005/2006

Veranstalter: Dr. Piotr Krysta
Vorlesung: Montag, 16:15 - 17:45, HG 1, HS 3
Mittwoch, 14:15 - 15:45, HG 1, HS 4
Übung: Mittwoch, 16:00 - 17:30, GB IV, R. 113
Beginn: 17. Oktober 2005
DPO 1996: Die Vorlesung kann als Teil verschiedener Vertiefungsgebiete geprüft werden.
DPO 2001: Die Vorlesung kann als Teil des Schwerpunktgebietes "Algorithmen, Komplexität und formale Modelle" geprüft werden.

Important Notice

This course will be given in English. The lecturing style, however, will be interactive enough so that the students can fully follow and understand the material.

Tutorials (Übungen)

Follow this link.

Contents

This will be a self-contained course on optimization, with an emphasis on basic ideas and principles. It will cover selected material contained in the books listed below. We will start from some basic problems and algorithms, and as the course proceeds we will advance to more sophisticated techniques, such as mathematical programming. Then we will focus on hard optimization problems and, in particular, applications of mathematical programming to those problems.

A preliminary (and not complete) list of topics is given below. The first list contains some specific "easy" problems, i.e., problems which are solvable in polynomial time.

  • matching and generalizations: weighted matching, b-matching
  • matroids and generalizations: bases, matroid intersection, submodular functions

    • The second list is on mathematical programming in general.

  • polyhedra, duality, linear programming, Simplex algorithm, Ellipsoid algorithm
  • semidefinite programming, quadratic programming, and convex programming
  • integer linear programming, totally unimodular matrices, total dual integrality

    • The third list has problems which are hard, and, in particular, NP-hard or even hard to approximate in polynomial time. We will first review the theory of NP-completeness, and then will study the approximability of the following specific problems. We will use some of the tools introduced in the mathematical programming part.

  • network design problems: Steiner forest and Steiner network problems
  • independent sets, set packing, and generalizations, multicut and sparsest cut
  • facility location and k-median, max-cut via semidefinite programming

    • If time permits we will also cover some extra topics not included in these books, related to the algorithmic mechanism design - a very recent, exciting area with applications to Electronic Commerce and the Internet. This part of the course will mostly be based on some recent research papers. In particular, we plan to cover the following topics.

  • truthful multi-unit auctions and multi-unit combinatorial auctions
  • scheduling and network design with selfish agents.

    • Literature

    [1] D.P. Bertsimas and J.H. Tsitsiklis. An Introduction to Linear Optimization. Athena Scientific, 1997.

    [2] V. Chvatal. Linear Programming. Freeman, 1983.

    [3] W.J. Cook, W.H. Cunningham, W.R. Pulleyblank and A. Schrijver. Combinatorial Optimization. John Wiley & Sons, Inc, 1998.

    [4] M. Groetschel, L. Lovasz and A. Schrijver. Geometric Algorithms and Combinatorial Optimization. 2nd Edition. Springer-Verlag, Berlin, 1993.

    [5] B. Korte and J. Vygen. Combinatorial Optimization, Theory and Algorithms. Springer-Verlag, Berlin, 2002.

    [6] M. Padberg. Linear Optimization and Extensions. Springer-Verlag, Berlin, 1995.

    [7] C.H. Papadimitriou and K. Steiglitz. Combinatorial Optimization: Algorithms and Complexity. Dover Publications, reprint 1998.

    [8] A. Schrijver. Theory of linear and integer programming. John Wiley & Sons, New York 1986.

    [9] V.V. Vazirani. Approximation Algorithms. Springer-Verlag, Berlin, 2001.