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
E-mailgaertner@inf.ethz.ch
URLhttp://people.inf.ethz.ch/gaertner/
DepartmentComputer Science
RelationshipAdjunct Professor

NumberTitleECTSHoursLecturers
252-1426-00LApproximation Algorithms and Semidefinite Programming Information 7 credits3V + 2U + 1AB. Gärtner, J. Matousek
AbstractOver 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.
ObjectiveStudents 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.
ContentThe 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 notesThe lecture will follow (parts of) the book "Approximation Algorithms and Semidefinite Programming" by the lecturers (see literature).
LiteratureBernd 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 / NoticeBasic knowledge in linear algebra and analysis; the ability to fill in routine details in proofs;
252-4202-00LSeminar in Theoretical Computer Science Information 2 credits2SE. Welzl, B. Gärtner, M. Hoffmann, J. Lengler, A. Steger, U. Wagner
AbstractPresentation of recent publications in theoretical computer science, including results by diploma, masters and doctoral candidates.
ObjectiveTo get an overview of current research in the areas covered by the involved research groups. To present results from the literature.
401-5900-00LOptimization and Applications Information 0 credits2KR. Weismantel, K. Fukuda, B. Gärtner, D. Klatte, J. Lygeros, M. Morari, K. Schmedders
AbstractLectures on current topics in optimization.
ObjectiveThis lecture series introduces graduate students to ongoing research activities (including applications) in the domain of optimization.
ContentThis 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.