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-02-05 16:23:15
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
-
-
-
-
Application Area (Only necessary and eligible for the Master degree in Applied Mathematics. One of the application areas specified must be selected for the category Application Area for the Master degree in Applied Mathematics. At least 8 credits are required in the chosen application area. Credits from other application areas cannot be recognised for further application areas.)
-
Electives (For the Master's degree in Applied Mathematics the following additional condition (not manifest in myStudies) must be obeyed: At least 15 of the required 28 credits from core courses and electives must be acquired in areas of applied mathematics and further application-oriented fields.)
-
-
Selection: Theoretical Computer Science, Discrete Mathematics (In the Master's programme in Mathematics 401-3052-05L Graph Theory is eligible as an elective course, but only if 401-3052-10L Graph Theory isn't recognised for credits (neither in the Bachelor's nor in the Master's programme). For the category assignment take contact with the Study Administration Office ( ) after having received the credits.)
-
-
-
-
-
-
-
-