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

Introduction

 

Contact

 

Name E-Mail 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).