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)