Forschungsinstitut für Diskrete Mathematik

Graduate Seminar on Discrete Optimization (S4C1)

Summer 2011

Graph Partitioning

Class hours: Mondays 14:15-15:45. Approval talks: 12:30-14:00

Divide-and-conquer is a standard algorithmic approach. When applied to problems on graphs, it requires to partition the graph appropriately. Often we ask for a partition of the vertex set into subsets of approximately equal size such that relatively few edges have their endpoints in different sets. This seminar discusses such balanced graph partitioning problems, their approximability, and their use for designing approximation algorithms.
The seminal work of Leighton and Rao [1999] revealed a tight connection to multi-commodity flows and showed that many balanced graph partitioning problems can be approximated up to a factor of O(log n), where n is the number of vertices of the graph. Arora, Rao, and Vazirani [2009] improved this to O(log ½ n). We discuss these papers, extensions, applications, and approaches to related problems.

Number Approval talk Talk Name Topic Mentoring
1 21.3.
4.4. Andreas Wierz Approximating fractional multicommodity flow Christoph Bartoschek
2 28.3.
11.4. Philipp Ochsendorf Multicommodity max-flow min-cut theorems and sparsest cuts Markus Struzyna
3 4.4.
18.4. Levin Keller Approximation algorithms based on sparsest cuts Markus Struyzna
4 11.4.
2.5. Andreas Billstein Metric embedding and sparsest cuts Dirk Müller
5 18.4.
9.5. Vincent Wisdorf Applications to feedback arc sets and balanced cuts Christoph Bartoschek
6 2.5.
16.5. Daniel Rotter O(log½ n)-approximation for sparsest cut Jan Schneider
7 9.5.
23.5. Anna-Klara Großwendt Finding well-represented sets in l22-representations Jan Schneider
8 16.5.
30.5. Christian Reinecke Expander Flows Jan Schneider
9 23.5.
6.6. Maximilian Lorse O(log½ n) approximation to sparsest cut in Õ(n2) time Jens Maßberg
10 30.5.
20.6. Pascal Welke Graph partitioning using single commodity flows Jens Maßberg
11 6.6.
27.6. Javier Garcia-Rodriguez Fast approximate graph partitioning algorithms Michael Gester
12 20.6.
4.7. Miguel Moreno Partitioning graphs into balanced components Christian Schulte
13 27.6.
11.7. Christian Theodor Beckers O(log n)-approximation of the graph bisection problem Ulrike Suhl

List of papers used for this seminar

Prof. Dr. B. Korte,
Prof. Dr. J. Vygen,
Prof. Dr. S. Hougardy,
Jun.Prof. Dr. T. Nieberg,
Jun.Prof. Dr. S. Held,
Dr. U. Brenner