Institute of Operating Systems and Computer Networks
- News
- About us
- Connected and Mobile Systems
- Distributed Systems
- Algorithms
- Microprocessor Lab
- Education
- Services
- Spin-Offs
- Research Cooperations
  - IST.hub

Master-Seminar Algorithmik

Semester	Winter 2016/2017 Summer 2023 Winter 2022/2023 Summer 2022 Winter 2021/2022 Summer 2021 Winter 2020/2021 Summer 2020 Winter 2019/2020 Summer 2019 Winter 2018/2019 Summer 2018 Winter 2017/2018 Summer 2017 Summer 2016
Module #	INF-STD-18, INF-STD-20
Event #	INF-ALG-019, INF-ALG-029
Programmes	Computer Science Master, Business Information Systems Master, Computer and Communication Systems Engineering Master
IBR Group	ALG (Prof. Fekete)
Type	Seminar
Lecturer	Prof. Dr. Sándor P. Fekete Abteilungsleiter s.fekete[[at]]tu-bs.de +49 531 3913111 Room 335
Assistants	Dr. Victor Alvarez Ehemaliger Wissenschaftlicher Mitarbeiter Dr. Phillip Keldenich Wissenschaftlicher Mitarbeiter keldenich[[at]]ibr.cs.tu-bs.de +49 531 3913112 Room 318 PD Dr. Christian Scheffer Ehemaliger Wissenschaftlicher Mitarbeiter scheffer[[at]]ibr.cs.tu-bs.de Dr. Arne Schmidt Wissenschaftlicher Mitarbeiter aschmidt[[at]]ibr.cs.tu-bs.de +49 531 3913115 Room 319 Dr. Dominik Krupke Wissenschaftlicher Mitarbeiter krupke[[at]]ibr.cs.tu-bs.de +49 531 3913116 Room 332 Christian Rieck Wissenschaftlicher Mitarbeiter rieck[[at]]ibr.cs.tu-bs.de +49 531 3913114 Room 314
Credits	5
Hours	0+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 ] 24.10.2016, 13:00 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: Google Scholar ACM Digital Library Citeseer (Research Index) Citation Index DBLP Universitätsbibliothek der TU-Braunschweig Ausarbeitung und Vortrag: Tipps+Tricks zu (La)TeX Templates
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.