Algorithmen & Komplexität

Informatik 1

Arbeitsgruppe

Forschung

Lehre

Diverses

Christoph Grüne Lehrstuhl für Informatik 1 Fachgruppe Informatik RWTH Aachen Ahornstrasse 55, E1, Raum 4021 52074 Aachen Tel.: +49 241 80 21104 Email: [lastname][AT]algo.rwth-aachen.de

---

Webseiten

https://reductions.network

reductions.network - Ein Kompendium von Reduktionen. Auf dieser Website werden Reduktionen und Probleme von verschiedenen Komplexitätsklassen dargestellt. Falls Du eine Reduktion oder ein Problem nachschauen möchtest, wirst Du hier bestimmt fündig. Wenn nicht, freue ich mich über Beiträge!

---

Publikationen

• The Complexity of Blocking All Solutions
  mit Lasse Wulf
  arXiv, 2025
  [arXiv]


• On the Complexity of Recoverable Robust Optimization in the Polynomial Hierarchy
  mit Lasse Wulf
  arXiv, 2024
  [arXiv]


• Completeness in the Polynomial Hierarchy for many natural Problems in Bilevel and Robust Optimization.
  mit Lasse Wulf
  arXiv, 2024
  [arXiv]


• The Complexity Classes of Hamming Distance Recoverable Robust Problems.
  LATIN 2024
  [conference] [arXiv]


• The Complexity of Online Graph Games.
  mit Janosch Fuchs and Tom Janßen
  SOFSEM 2024
  [conference] [arXiv]


• The Complexity of Graph Exploration Games.
  mit Janosch Fuchs and Tom Janßen
  arXiv, 2023
  [arXiv]


• Solving the Dial-a-Ride Problem for Railway Traffic by Means of Heuristics.
  mit Stephan Zieger
  SMARTGREENS/VEHITS (Selected Papers) 2022
  [journal]


• Demand-responsive Scheduling in Railway Transportation.
  mit Stephan Zieger
  VEHITS 2022
  [conference]

---

Lehre

• WS24/25
  • Vorlesung: Berechenbarkeit und Komplexität
  • Seminar: Advanced Algorithms
• SS24
  • Seminar: The Cake is a Lie: Cake-Cutting Algorithms
• WS23/24
  • Vorlesung: Berechenbarkeit und Komplexität
• WS22/23
  • Vorlesung: Effiziente Algorithmen
• SS22
  • Proseminar: Geschichte der Informatik
• WS21/22
  • Vorlesung: Berechenbarkeit und Komplexität
  • Proseminar: Optimierungsprobleme
• WS19/20
  • Vorlesung: Optimierung B

---

Nichtwissenschaftliche Webseiten

https://mateconnaisseur.de

Der Mate-Connaisseur. In Deutschlands erstem Mate-Blog berichten wir unabhängig über Mate-Eistees aus der gesamten Welt. Wir unterziehen jede Mate einem standardisierten Geschmackstest und schildern unsere Erlebnisse in einem Artikel. Unser Ziel ist es jeden Mate-Eistee auf der gesamten Welt probiert zu haben.