##
Seminar Algorithms and Complexity Reading Group

Summer Term 2023

### Seminar topic: Advanced Graph Algorithms

### Seminar description

We will present and discuss material (papers and lecture notes) on advanced topics in graph algorithms. We will meet weekly on Wednesday from 16:15 - 18:00. Each week, we will discuss one topic. A (tentative) schedule of topics that we will discuss will soon be published on this website. Each student has to lead the discussion on one of the topics. The focus will be on a detailed understanding of the content in detail rather than on a polished presentation. The presentations can therefore be done on the board, slides are not mandatory.

### Tentative Schedule

- Weekly seminar meeting: Wednesdays, 16:15 - 18:00, room 106-00-007

**19.04.2023:**Introductory meeting and discussion of paper A Graph-Theoretic Game and Its Application to the k-Server Problem by Noga Alon, Richard M. Karp, David Peleg, and Douglas West

*The paper in particular introduces an algorithm to compute a spanning tree of a (weighted) graph such that the average stretch of the edges of G is small.***26.04.2023: No seminar meeting****03.05.2023: Assignment of papers, Brief introduction to spectral graph theory I****10.05.2023: Brief introduction to spectral graph theory II****17.05.2023: (student presentation)**Discussion of survey paper**The Multiplicative Weights Update Method: a Meta Algorithm and Applications**by Sanjeev Arora, Elad Hazan, and Satyen Kale*(presented by Tim Oswald and Nick Göckel)***24.05.2023: (student presentation)**Discussion of paper**A Tight Bound on Approximating Arbitrary Metrics by Tree Metrics**by Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar; J. of Computer and System Sciences 69 (3), 2004*(presented by Fateh Aslam and Rawel Singh*)**31.05.2023: No seminar meeting**(Pfingstpause)**07.06.2023: (student presentation)**Discussion of paper**Optimal Hierarchical Decompositions for Congestion Minimization in Networks**by Harald Räcke; ACM Symposium on Theory of Computing (STOC), 2008*(presented by Fatlum Sadiku and Matthias Zumkeller*)**14.06.2023: (student presentation)**Discussion of paper**Randomized Approximation Schemes for Cuts and Flows in Capacitated Graphs**by András A. Benczúr and David R. Karger; SIAM J. on Computing 44 (2), 2015*(presented by Ioannis Nezis and Friedrich Hoffmann*)**21.06.2023: (student presentation)**Discussion of paper**A Simple and Linear Time Randomized Algorithm for Computing Sparse Spanners in Weighted Graphs**by Surender Baswana and Sandeep Sen; Random Structures and Algorithms 30 (4), 2007*(presented by Hans Albert and Marcel Ebbinghaus*)**28.06.2023: (student presentation)**Discussion of paper**Simple Parallel and Distributed Algorithms for Spectral Graph Sparsification**by Ioannis Koutis; ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2014*(presented by Aaron Würth, Lukas Kneissl and Xinyu Jiang*)**05.07.2023:**Discussion of paper**Fast Approximation Algorithms for Cut-based Problems in Undirected Graphs**by Aleksander Madry; IEEE Symposium on Foundations of Computer Science (FOCS), 2010**12.07.2023: no seminar****19.07.2023: (student presentation)**Discussion of paper**Nearly Maximum Flows in Nearly Linear Time**by Jonah Sherman; IEEE Symposium on Foundations of Computer Science (FOCS), 2013*(presented by Florian Pollitt and Gustav Schmid*)

### Seminar Papers and Material

We will discuss the content of some papers and also some content of
the lecture notes of a recent

**Lecture Notes of "Advanced Graph Algorithms and Optimization" lecture**by Rasmus Kyng and Maximilian Probst Gutenberg**A Tight Bound on Approximating Arbitrary Metrics by Tree Metrics**by Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar; J. of Computer and System Sciences 69 (3), 2004**Optimal Hierarchical Decompositions for Congestion Minimization in Networks**by Harald Räcke; ACM Symposium on Theory of Computing (STOC), 2008**Randomized Approximation Schemes for Cuts and Flows in Capacitated Graphs**by András A. Benczúr and David R. Karger; SIAM J. on Computing 44 (2), 2015**Fast Approximation Algorithms for Cut-based Problems in Undirected Graphs**by Aleksander Madry; IEEE Symposium on Foundations of Computer Science (FOCS), 2010**Nearly Maximum Flows in Nearly Linear Time**by Jonah Sherman; IEEE Symposium on Foundations of Computer Science (FOCS), 2013**The Multiplicative Weights Update Method: a Meta Algorithm and Applications**by Sanjeev Arora, Elad Hazan, and Satyen Kale**A Simple and Linear Time Randomized Algorithm for Computing Sparse Spanners in Weighted Graphs**by Surender Baswana and Sandeep Sen; Random Structures and Algorithms 30 (4), 2007**Simple Parallel and Distributed Algorithms for Spectral Graph Sparsification**by Ioannis Koutis; ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2014