VVZ API is not affiliated with ETH Zurich. Data might be outdated or incorrect. Please view the official ETHZ Vorlesungsverzeichnis for binding information.
Advanced Graph Algorithms and Optimization
Last Updated: 2026-06-01 11:33:07
Abstract
This course will cover a number of advanced topics in optimization and graph algorithms.
Objective
The course will take students on a deep dive into modern approaches to graph algorithms using convex optimization techniques. By studying convex optimization through the lens of graph algorithms, students should develop a deeper understanding of fundamental phenomena in optimization. The course will cover some traditional discrete approaches to various graph problems, especially flow problems, and then contrast these approaches with modern, asymptotically faster methods based on combining convex optimization with spectral and combinatorial graph theory.
Content
Students should leave the course understanding key concepts in optimization such as first and second-order optimization, convex duality, multiplicative weights and dual-based methods, acceleration, preconditioning, and non-Euclidean optimization. Students will also be familiarized with central techniques in the development of graph algorithms in the past 15 years, including graph decomposition techniques, sparsification, oblivious routing, and spectral and combinatorial preconditioning.
Resources
Learning Materials (Links)
- Main link
- Information
General Information
- Language
- English
- Levels
- MSC , WBZ
- Frequency
- Yearly recurring
Examination
- Type
- graded semester performance
Course Components
| Type | Title | Time & Place | Hours |
|---|---|---|---|
| lecture | Advanced Graph Algorithms and Optimization |
|
3 h weekly |
| exercise | Advanced Graph Algorithms and Optimization |
|
3 h weekly |
| independent project | Advanced Graph Algorithms and Optimization | No time listed | 3 h weekly |
Offered In
-
-
-
-
Anwendungsgebiet (Nur für das Master-Diplom in Angewandter Mathematik erforderlich und anrechenbar. In der Kategorie Anwendungsgebiet für den Master in Angewandter Mathematik muss eines der zur Auswahl stehenden Anwendungsgebiete gewählt werden. Im gewählten Anwendungsgebiet müssen mindestens 8 KP erworben werden. Kreditpunkte aus anderen Anwendungsgebieten sind nicht für weitere Anwendungsgebiete anrechenbar.)
-
Wahlfächer (Für das Master-Diplom in Angewandter Mathematik ist die folgende Zusatzbedingung (nicht in myStudies ersichtlich) zu beachten: Mindestens 14 KP der erforderlichen 26 KP aus Kern- und Wahlfächern müssen aus Bereichen der angewandten Mathematik und weiteren anwendungsorientierten Gebieten stammen.)
-
Wahlfächer aus Bereichen der angewandten Mathematik ... (vollständiger Titel: Wahlfächer aus Bereichen der angewandten Mathematik und weiteren anwendungsorientierten Gebieten)
-
Auswahl: Theoretische Informatik, diskrete Mathematik (Im Master-Studiengang Mathematik ist auch 401-3052-05L Graph Theory als Wahlfach anrechenbar, aber nur unter der Bedingung, dass 401-3052-10L Graph Theory nicht angerechnet wird (weder im Bachelor- noch im Master-Studiengang). Wenden Sie sich für die Kategoriezuordnung nach dem Verfügen des Prüfungsresultates an das Studiensekretariat ( ).)
-
-
-
-
-
-
-
-