Summer 2011
Graph Partitioning
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 l 2 2 -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 Õ(n 2 ) 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
- A regular participation in the talks and an active collaboration are mandatory for passing the seminar.
- The talks will take approximately 75 minutes. The remaining 15 minutes are intended for a discussion.
- Each participant has to write a summary consisting of one or two pages.
- Each participant has to give an approval talk (typically three weeks before the regular talk). Passing the approval talk is a prerequisite for giving the regular seminar talk.
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