Algorithms & Complexity

Computer Science 1

Group

Research

Teaching

Misc

Christoph Grüne Computer Science 1 Dept. of Computer Science RWTH Aachen University Ahornstrasse 55, E1, Room 4021 D-52074 Aachen, Germany Phone: +49 241 80 21104 Email: [lastname][AT]algo.rwth-aachen.de

---

Websites

https://reductions.network

reductions.network - A Compendium of Reductions. On this website many reductions and problems for various complexity classes are presented. If you are searching for information on a reduction or problem, you will probably find, what you are looking for. And if not, I am always happy to receive contributions!

---

Publications

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


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


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


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


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


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


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


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

---

Teaching

• WS24/25
  • Lecture: Berechenbarkeit und Komplexität (Computability and Complexity)
  • Seminar: Advanced Algorithms
• SS24
  • Seminar: The Cake is a Lie: Cake-Cutting Algorithms
• WS23/24
  • Lecture: Berechenbarkeit und Komplexität (Computability and Complexity)
• WS22/23
  • Lecture: Effiziente Algorithmen (Efficient Algorithms)
• SS22
  • Proseminar: Geschichte der Informatik (History of Computer Science)
• WS21/22
  • Lecture: Berechenbarkeit und Komplexität (Computabilty and Complexity)
  • Proseminar: Optimierungsprobleme (Optimization Problems)
• WS19/20
  • Lecture: Optimierung B (Optimization B)

---

Non-Scientific Websites

https://mateconnaisseur.de

The Mate-Connaisseur. In Germany's first mate blog, we report independently on mate ice teas from all over the world. We subject every mate to our standardized taste test and describe our experiences in an article. Our goal is to taste every mate ice tea existing in the whole world.