Arbeitsgruppe Algorithmen und Komplexität

Informationen zum Interdisziplinären Seminar (Operations Research - Theoretische Informatik)

 

Alle Studierenden, die am Seminar teilnehmen, halten zu ihrem Thema während des Semesters einen Vortrag und fertigen (ca. bis zum Ende des Semesters) eine schriftliche Ausarbeitung dazu an. Zur Auswahl stehen folgende Artikel, die als Themengrundlage dienen sollen:

  1.  ,,Nondeterministic Extensions of the Strong Exponential Time Hypothesis and Consequences for Non-reducibility" von Carmosino et al. (https://dl.acm.org/doi/pdf/10.1145/2840728.2840746)
  2. ,,Block-structured Integer Programming: Can we Parameterize without the Largest Coefficient?" von Chen et al. (https://arxiv.org/pdf/2011.02826.pdf)
  3. ,,A 3-Approximation Algorithm for Maximum Independent Set of Rectangles" von Gálvez et al. (https://arxiv.org/pdf/2106.00623.pdf)
  4. ,,Tight Complexity Lower Bounds for Integer Linear Programming with Few Constraints" von Knop et al. (https://dl.acm.org/doi/pdf/10.1145/3397484)
  5. ,,Tight running times for minimum ?q-norm load balancing: beyond exponential dependencies on 1/ε" von Chen et al. (https://arxiv.org/pdf/2107.06261.pdf)
  6. ,Parameterized Problems Complete for Nondeterministic FPT time and Logarithmic Space" von Bodlaender et al. (https://arxiv.org/pdf/2105.14882.pdf)

 

Interessierte Studierende melden sich bitte bei Prof. Jansen (kj@informatik.uni-kiel.de) und Kai Kahler (kka@informatik.uni-kiel.de).