Seminar Combinatorial Optimization: Graph Decompositions
Important Dates
| Topic assignment | October 16, 2019 | 10-12 (c.t.) | Zuse Institute Berlin, Takustr. 7, Seminar Room 2006 |
| Kick-off | November 20, 2019 | 10-12 (c.t.) | Zuse Institute Berlin, Takustr. 7, Seminar Room 2006 |
| Summary Deadline | January 19, 2020 | ||
| Seminar talks | February 18 and 19, 2020 | 9-17 (s.t.) | Zuse Institute Berlin, Takustr. 7, Lecture Hall 2005 |
Block Seminar Schedule
| Date | Time | Student | Paper |
|---|---|---|---|
| Tue, Feb 18 | 09.00 - 10.00 | Sarah Burchert | Combinatorial Optimization on Graphs of Bounded Treewidth (Bodlaender, Koster) |
| 10.00 - 11.00 | Enrico Bortoletto | On Exact Algorithms for Treewidth (Bodlaender et al.) | |
| 11.00 - 12.00 | Sampada Kolhatkar | Graph minors. II. Algorithmic aspects of tree-width (Robertson, Seymour) | |
| 12.00 - 13.00 | Lunch Break | ||
| 13.00 - 14.00 | Ellinor Janssen | Tour merging via branch-decomposition (Cook, Seymour) | |
| 14.00 - 15.00 | William Bitsch | On the complexity of the maximum cut problem (Bodlaender, Jansen) | |
| 15.00 - 15.15 | Coffee Break |
| |
| 15.15 - 16.15 | Lara Glessen | Improved Steiner tree algorithms for bounded treewidth (Chimani, Mutzel, Zey) | |
| Wed, Feb 19 | 09.00 - 10.00 | Mara Nehring | Call routing and the ratcatcher (Robertson, Seymour) |
| 10.00 - 11.00 | Julia Kraus | A separator theorem for planar graphs (Lipton, Tarjan) | |
| 11.00 - 12.00 | Thomas Nagel | An Exact Combinatorial Algorithm for Minimum Graph Bisection (Delling et al.) | |
| 12.00 - 13.00 | Lunch Break | ||
| 13.00 - 14.00 | Paul Lazureanu | Graph Bisection with Pareto-Optimization (Hamann, Strasser) | |
| 14.00 - 15.00 | Sukhmani Kaur Bedi | Faster Transit Routing by Hyper Partitioning (Delling et al.) | |
| 15.00 - 15.15 | Coffee Break |
| |
| 15.15 - 16.15 | Sandeep Kaur | Normalized Cuts and Image Segmentation (Shi, Malik) |
Slides
Contact
| Name | Room | |
| Dr. Niels Lindner | lindner@zib.de | ZIB 3007 |
| Ricardo Euler | euler@zib.de | ZIB 3023 |
Summary Instructions
Please submit your written summary of your topic no later than January 19, 2020. This summary is mandatory for a successful participation and accounts for a third of the final grade.
Formal requirements:
* 5-8 pages
* English or German
* LaTeX in printing quality, i.e., look at your language, typos and formatting (in particular badboxes and math/text mode issues)
* include your name, the paper's title and authors on the first page
Content requirements:
* Explain the main results of the paper. Try to formulate one or few key highlights.
* Motivate the key problem and discuss the important notions, even if they are not introduced in the paper.
* Formulate the main problem and/or model in a mathematically precise way.
* For algorithmic results: Explain how and why the algorithm works.
* For theoretic results: Highlight the main proof ideas. There is no need to copy long or less important proofs.
* Make clear your contribution to the summary: Use your own words. Do not copy from the original paper. Try to add own examples, explanations, pictures etc.
* Do not copy figures or tables from the paper if they are unnecessary or you do not reference them in text.
Additionally, you are encouraged to:
* Add a (short) literature review: How does your paper improve on previous results? In turn, have the results of your paper been improved by later publications? How does your paper fit into the research landscape?
* Finish your summary with your own comments to the paper. What did you like? What is missing? What do you think of the methods? If you had to continue research on your paper's topic, what would you investigate next?
Send the summary as PDF file to lindner@zib.de.
Description
Optimierungsprobleme auf Graphen sind in Theorie und Praxis allgegenwärtig. Häufig bietet sich für große Graphen eine Zerlegung in Probleme auf Teilgraphen an, um das Gesamtproblem nach dem Teile-und-herrsche-Prinzip zu lösen. Dabei kann zum einen nur der Graph als solches zerlegt werden, zum anderen eröffnen sich auch neue algorithmische Perspektiven. In diesem Seminar behandeln wir sowohl theoretische Ansätze zur Graphzerlegung als auch konkrete zerlegungsbasierte Lösungsmethoden für kombinatorische Optimierungsprobleme.
Insbesondere betrachten wir:
- Graphpartitionierung bzw. balancierte Schnitte
- Baum- und Branchzerlegungen
Das Seminar wird als Blockseminar durchgeführt.
- Themenvergabe: Mittwoch, 16.10., 10 Uhr c.t., ZIB, Seminarraum 2006
- Kick-off: tba
- Blockseminar: tba
Beim zweiten Treffen (Kick-off) sollen die Studenten einen Kurzvortrag (max. 5 Minuten) über ihr Thema halten.
Die Vorträge am Tag des Blockseminars sollen eine Dauer von 45 Minuten haben. Zur erfolgreichen Teilnahme gehört außerdem die Anfertigung einer schriftlichen Ausarbeitung der wesentlichen Inhalte in professioneller Qualität (LaTeX, 5-8 Seiten).
Voraussetzungen: Grundlagen der Graphentheorie, etwa im Umfang von Diskrete Mathematik I
Ergänzend empfiehlt sich fakultativ auch der Besuch der Vorlesungen Optimierung I (Ralf Borndörfer) oder Optimale Touren in Graphen (Niels Lindner).