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 |