TU BRAUNSCHWEIG
| Carl-Friedrich-Gauß-Faculty | Computer Science
Informatikzentrum

Master-Seminar Algorithmik

Module #INF-STD-18, INF-STD-20
Event #INF-ALG-019, INF-ALG-029
ProgrammesMaster Informatik, Master Wirtschaftsinformatik, Master Elektrotechnik
IBR Group(s)ALG (Prof. Fekete)
TypeSeminar
Lecturer
PhotoProf. Dr. Sándor P. Fekete
Abteilungsleiter
s.fekete[[at]]tu-bs.de
+49 531 3913111
Room 335
Assistants
PhotoDr. Victor Alvarez
Ehemaliger Wissenschaftlicher Mitarbeiter
alvarez[[at]]ibr.cs.tu-bs.de
PhotoPhillip Keldenich
Wissenschaftlicher Mitarbeiter
keldenich[[at]]ibr.cs.tu-bs.de
+49 531 3913112
Room 318
PhotoDr. Christian Scheffer
Wissenschaftlicher Mitarbeiter
scheffer[[at]]ibr.cs.tu-bs.de
+49 531 3913113
Room 331
PhotoArne Schmidt
Wissenschaftlicher Mitarbeiter
aschmidt[[at]]ibr.cs.tu-bs.de
+49 531 3913115
Room 319
PhotoDominik Krupke
Wissenschaftlicher Mitarbeiter
krupke[[at]]ibr.cs.tu-bs.de
+49 531 3913116
Room 315
PhotoChristian Rieck
Wissenschaftlicher Mitarbeiter
rieck[[at]]ibr.cs.tu-bs.de
+49 531 3913114
Room 314
Credits5
Hours0+2
Prerequisites Voraussetzungen für die Bearbeitung der einzelnen Themen sind jeweils individuell aufgeführt. Sind diese in Klammern gesetzt, sind sie zwar hilfreich, aber keine Voraussetzung.
Certificates Schriftliche Ausarbeitung und erfolgreicher Seminarvortrag. Die Note wird abhängig von der aktiven Teilnahme am Seminar sowie der Qualität des Vortrages und der Ausarbeitung bestimmt.
Registration Anmeldung zentral (über StudIP). Die Vorbesprechung für das Seminar erfolgt am 24.10.2016 um 13:00 Uhr im Besprechungsraum der Abteilung Algorithmik (IZ313).
Content Das Seminar Algorithmik beschäftigt sich dieses Semester mit einer Reihe von aktuellen Artikeln sowie Ausschnitten aus Büchern. Die genauen Themen sowie eine Abstract sind weiter unten aufgeführt.
Schedule
[ Subscribe Calendar | Download Calendar ]
DateDescription
24.10.2016, 13:00 Uhr Kickoff-Meeting (IZ313)
09.01.2017 Peer-Review
16.01.2017 Feedback
23.01.2017 Final Version
27.01.2017 Erste Vortragsversion
06.02.2017 Vorträge (IZ313)
References Literaturrecherche: Ausarbeitung und Vortrag:

Hinweise

Teilnehmerzahl

Es werden 4 Plätze für Studierende auf Masterniveau angeboten.

Ausarbeitung

Die Ausarbeitung soll etwa 8-10 Seiten lang sein. Generell interessiert uns, dass Sie da eine selbstverfasste Zusammenfassung eines selbst verstandenen Artikels abgeben. Wesentlich mehr als die genannte Seitenzahl sollte es nicht werden, immerhin geht es hier um die Kunst des Zusammenfassens. Wir erwarten, dass Sie selbstständig zusätzliche Quellen recherchieren.

Vortrag

Ihr Vortrag soll etwa 30 Minuten (reine Vortragszeit) dauern. Anschließend wird es eine kurze Diskussionsrunde mit Fragen geben. Das Medium ist frei, Sie können also Whiteboard, Overhead-Projektor, Beamer mit PowerPoint, Beamer mit PDF, oder was auch immer Sie für sinnvoll erachten, einsetzen. Natürlich sollten Sie bei exotischen Wünschen diese erstmal mit dem Betreuer klären, und unbedingt auch Programm-, Programmversions- und sonstige Kompatibilitätsfragen besprechen.

Themen für Masterstudenten

Grundsätzlich ist es im Masterbereich möglich, an aktuellen Forschungsthemen aus der Algorithmik zu arbeiten. Falls kein spezielles Thema gewünscht ist, wird nach Rücksprache mit dem Teilnehmer ein Thema aus einer Liste von Themen zugewiesen.

Die Themen dieses Semesters sind:

Gomory-Hu Trees

The network flow problem was first introduced by Ford Fulkerson who introduced the basic concept of flow, cut, etc. and provided the main tool, the maximum-flow minimum-cut theorem. Ford and Fulkerson wrote about the flow between two special points, the source and the sink. Mayeda then took up the multi-terminal problem, where flows are considered between all pairs of nodes in a network. In the discussed paper of Gomory and Hu it is continued with the multi-terminal problem, giving results on realizability, analysis and synthesis.

The Geometric Maximum Traveling Salesman Problem

The classical Traveling Salesman Problem asks for a tour through a given set of vertices such that the total distance of this tour is minimized. Instead of minimizing the total length, one can also asks for a maximum total tour length. It can be shown that such an optimal tour can be computed in time O(n) if distances are determined by the Manhatten metric, while it is NP-hard under Euclidean distances.

Algorithms for Ham-Sandwich Cuts

Given disjoint sets P_1, P_2, ..., P_d in R^d with n points in total, a ham sandwich cut is a hyperplane that simultaneously bisects the P_i. There is an algorithm for finding ham-sandwich cuts in every dimension d>1. When d=2, the algorithm is optimal, having complexity O(n). For dimension d>2, the bound on the running time is proportional to the worst-case time needed for constructing a level in an arrangement of n hyperplanes in dimension d-1.

Generalizing Ham-Sandwich Cuts to Equitable Subdivisions

Given gn red points and gm blue points in the plane in general position, there exists an equitable subdivision of the plane into g disjoint convex polygons, each of which contains n red points and m blue points.This is a generalization of the Ham Sandwich Theorem for the plane. There is also an efficient algorithm for constructing such equitable subdivisions.

last changed 2016-11-01, 17:22 by Phillip Keldenich
printemailtop