Bernd Gärtner: Catalogue data in Spring Semester 2012 |
Name | Prof. Dr. Bernd Gärtner |
Address | Inst. f. Theoretische Informatik ETH Zürich, OAT Z 15 Andreasstrasse 5 8092 Zürich SWITZERLAND |
Telephone | +41 44 632 70 26 |
Fax | +41 44 632 10 63 |
gaertner@inf.ethz.ch | |
URL | http://people.inf.ethz.ch/gaertner/ |
Department | Computer Science |
Relationship | Adjunct Professor |
Number | Title | ECTS | Hours | Lecturers | |
---|---|---|---|---|---|
252-1426-00L | Approximation Algorithms and Semidefinite Programming | 7 credits | 3V + 2U + 1A | B. Gärtner, J. Matousek | |
Abstract | Over the last fifteen years, semidefinite programming has become an important tool for approximate solutions of hard combinatorial problems. In this lecture, we introduce the foundations of semidefinite programming, we present some of its applications in (but not only in) approximation algorithms, and we show how semidefinite programs can efficiently be solved. | ||||
Objective | Students should understand that semidefinite programs form a well-understood class of optimization problems that can (approximately) be solved in polynomial time and yet are powerful enough to yield good approximate solutions for hard combinatorial problems. | ||||
Content | The Goemans-Williamson MAXCUT algorithm. semidefinite programming, The Lovasz theta function, cone programming and duality, algorithms for semidefinite programming, advanced applications of semidefinite programming in approximation algorithms | ||||
Lecture notes | The lecture will follow (parts of) the book "Approximation Algorithms and Semidefinite Programming" by the lecturers (see literature). | ||||
Literature | Bernd Gärtner and Jiri Matousek: Approximation Algorithms and Semidefinite Programming, Springer, 2012 David P. Williamson and David B. Shmoys: The Design of Approximation Algorithms, Cambridge University Press, 2011 | ||||
Prerequisites / Notice | Basic knowledge in linear algebra and analysis; the ability to fill in routine details in proofs; | ||||
252-4202-00L | Seminar in Theoretical Computer Science | 2 credits | 2S | E. Welzl, B. Gärtner, M. Hoffmann, J. Lengler, A. Steger, U. Wagner | |
Abstract | Presentation of recent publications in theoretical computer science, including results by diploma, masters and doctoral candidates. | ||||
Objective | To get an overview of current research in the areas covered by the involved research groups. To present results from the literature. | ||||
401-5900-00L | Optimization and Applications | 0 credits | 2K | R. Weismantel, K. Fukuda, B. Gärtner, D. Klatte, J. Lygeros, M. Morari, K. Schmedders | |
Abstract | Lectures on current topics in optimization. | ||||
Objective | This lecture series introduces graduate students to ongoing research activities (including applications) in the domain of optimization. | ||||
Content | This lecture series is a forum for researchers interested in optimization theory and its applications. Speakers, invited from both academic and non-academic institutions, are expected to stimulate discussions on theoretical and applied aspects of optimization and related subjects. Of interest are efficient (or practical) algorithms for continuous and discrete optimization problems, complexity analysis of algorithms and associated decision problems, approximation algorithms, mathematical modeling and solution procedures for real-world optimization problems in science, engineering, industries, public sectors etc. |