Einladung zum

69. Workshop über Algorithmen und Komplexität „Theorietag“

28. und 29. Mai 2015, Technische Universität Ilmenau

Der 69. Workshop über Algorithmen und Komplexität der GI-Fachgruppen Komplexität (KP) und Algorithmen (ALGO) findet am 28. und 29. Mai 2015 an der Technischen Universität Ilmenau statt. Alle Interessierten sind herzlich eingeladen.

Vorläufiges Programm

Das Programm ist mitsamt einer Abstract-Sammlung als PDF hier erhältlich. Jeder Teilnehmer erhält die gedruckte Abstract-Sammlung zu Beginn des Workshops.

Donnerstag, 28. Mai. 2015

12:00 — 12:55 Brötchen, Kaffee
12:55 — 13:00 Begrüßung
13:00 — 13:30 Christian Komusiewicz Editing Graphs into few Cliques: Complexity, Approximation, and Kernelization Schemes
13:30 — 14:00 Maurice Chandoo Deciding Circular-Arc Graph Isomorphism in O(k + log n) Space
14:00 — 14:30 Jens M. Schmidt Computing Tutte Cycles
14:30 — 15:00 Kaffee
15:00 — 16:00 Eingeladener Vortrag: Uwe Schöning Local Search for Satisfaction
16:00 — 16:30 Kaffee
16:30 — 17:00 Robert Bredereck Large-Scale Election Campaigns: Combinatorial Shift Bribery
17:00 — 17:30 Moritz Gobbert Edge Hop (Ein Modell zur Komplexitätsanalyse von kombinatorischen Spielen)
17:30 — 18:00 Holger Thies Analytic Continuation in iRRAM
Ab 18:30 Gemeinsames Abendessen im Hotel Tanne

Freitag, 29. Mai 2015

09:00 — 09:30 Pascal Lenzner Selfish Network Creation: Think Global -- Act Local
09:30 — 10:00 Pavel Podlipyan Almost collisionless gathering
10:00 — 10:30 Christopher Mattern On Probability Estimation via Relative Frequencies and Discount
10:30 — 11:00 Kaffeepause
11:00 — 11:30 Andreas Jakoby How to Generate Random Graphs with given Vertex-Cover Size
11:30 — 12:00 Ralf Rothenberger Ultra-Fast Load Balancing in Scale-Free Networks
12:00 — 12:30 Naveen Kumar Goswami Cardinality-Based Algorithms for the Vertex Cover Problem

Die Vortragssprache ist wahlweise Deutsch oder Englisch.

Veranstaltungsort: Zusebau, Raum 4005 (siehe Campusplan)

Eingeladener Vortrag: Uwe Schöning, Ulm: Local Search for Satisfaction

Zusammenfassung: Das Erfüllbarkeitsproblem SAT ist NP-vollständig und daher scheinen entsprechende Algorithmen, zumindest im schlechtesten Fall, exponentielle Laufzeit zu haben. Für die ebenfalls NP-vollständige "3 Literale pro Klausel"-Variante 3-SAT trifft diese Aussage ebenfalls zu, jedoch lassen sich in diesem Fall Algorithmen der Laufzeit c^n angeben, wobei die Konstante c wesentlich kleiner als 2 ist. Hier sind es vor allem Algorithmen, die auf dem einfachen Lokale Suche-Prinzip beruhen, die hier erfolgreich sind. Neben den theoretischen Ergebnissen, die sich um die kleinste solche Konstante c bemühen, soll gezeigt werden, wie diese "theoretischen Algorithmen" in "praktische" überführt werden können, so dass wir auch bei der "SAT Competiton" in den letzten Jahren Erfolge verbuchen konnten.

Übernachtung

Im Hotel Tanne ist ein kleines Zimmerkontingent verfügbar (62 Euro pro Nacht EZ, 84 Euro pro Nacht DZ, inklusive Frühstück, Sauna und WLAN). Anmeldeschluss hierfür ist der 15.05.2015. Bitte geben Sie bei der Reservierung das Stichwort „69. Theorietag“ an. Das Hotel ist etwa 2km vom Campus der TU Ilmenau entfernt.

Anfahrt

Siehe Anfahrtsplan auf den Seiten der TU Ilmenau. Vom Hotel Tanne zum Campus kann man in etwa 30 Minuten zu Fuß laufen. Außerdem fährt die Buslinie A im 20-Minuten-Takt vom Homburger Platz zum Campus der TU Ilmenau (Mensa). Achtung: Die Bushaltestelle liegt auf derselben Straßenseite wie das Hotel Tanne. Die Busse verkehren ab dem Homburger Platz immer xx:14, xx:34 und xx:54. Weitere Informationen finden Sie auf den Webseiten des Ilmenauer Nahverkehrs.

Anmeldung

Aus Organisationszwecken bitten wir um die Anmeldung von Vorträgen (mit kurzem Abstract) bzw. Teilnahmewünschen bis zum 15.05.2015.

Kontakt: Martin Dietzfelbinger, martin.dietzfelbinger@tu-ilmenau.de

Links der Fachgruppen: