Course CO2a: Combinatorial Optimization 2a 

Course description:
Combinatorial optimization is the investigation of design and planning problems in which discrete decisions must be made. The field originated in the 1950s with the work of Dantzig et al and Gomory on integer linear programming formulations for routing, scheduling and cutting stock problems. Other applications occur, e.g. in facility location, network and circuit design, and biomolecular systems.
The course gives an introduction into NP-hardness, and discusses approaches for dealing with NP-hard problems, like: approximation techniques; local search; probabilistic analysis; fixed parameterized tractability; exact algorithms.

Literature:
- C.H. Papadimitriou, K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Dover, 1998.
- In addition, some papers will be provided.

Prerequisites:
- Knowledge of basic linear algebra.
- Knowledge of network flow, linear programming and duality as, e.g., in V. Chvatal, Linear Programming, Freeman, 1983.

Examination:

Address of the lecturer:
Prof.dr. G.J. Woeginger
Dept. of Mathematics & Computer Science
Eindhoven University of Technology, P.O. Box 513, 5600 MB Eindhoven
Phone: 040 - 2472415 E-mail: gwoegi@win.tue.nl URL: www.win.tue.nl/~gwoegi