Ralf Rothenberger

Research Interests

My research interests include several topics of algorithmics and theoretical computer science.

• graph theory
  • graph algorithms
  • random graphs
  • scale-free networks
• satisfiability
  • random SAT models
  • phase transitions
  • proof complexity
• algorithms
  • random algorithms
  • load balancing
  • approximation algorithms

Projects

I have been involved in several past and ongoing projects of the Algorithm Engineering group.

• Scale-Free Satisfiability
• Optimizing Project Schedules
• Analysis of random geometric SAT instances
• Geometry in industrial model-checking SAT instances
• Efficient Shortest Paths on Portable Devices
• Finding a Parking Place Quickly

Teaching

As Advisor

• Optimizing Project Schedules (BSc Project, 2017/18)
• Analysis of random geometric SAT instances (MSc Project, Winter 2017/18)
• Geometry in industrial model-checking SAT instances (MSc Project, Winter 2017/18)
• Efficient Shortest Paths on Portable Devices (BSc-Projekt, 2016/17)
• Finding a Parking Place Quickly (BSc-Projekt, 2015/16)

Activities

Since 2017 I am a member of the HPI's board game club.

Past Activities:

• member of the HPI Research School on "Service-Oriented Systems Engineering"
• co-organizing the group's weekly Research Seminar
• member of the organization committee for the 13th Symposium on Future Trends in Service-Oriented Computing 2018
• member of the organization committee for the 12th Symposium on Future Trends in Service-Oriented Computing 2017

Code and Tools

Power-Law Random SAT generator

The algorithm for this generator was proposed by Ansótegui et al. in "Towards industrial-like random SAT instances" (IJCAI 2009).
We used this generator for the experiments in "Phase Transitions for Scale-Free SAT Formulas" (AAAI 2017) and "Bounds on the Satisfiability Threshold for Power Law Distributed Random SAT" (ESA 2017).

The code of our implementation can be found here.

Publications

2023

•  

  Nikfarjam, Adel; Rothenberger, Ralf; Neumann, Frank; Friedrich, TobiasEvolutionary Diversity Optimisation in Constructing Satisfying AssignmentsGenetic and Evolutionary Computation Conference (GECCO) 2023

  [ ][ ][ URL ][ DOI ][ Download ]

2021

•  

  Bläsius, Thomas; Friedrich, Tobias; Göbel, Andreas; Levy, Jordi; Rothenberger, RalfThe Impact of Heterogeneity and Geometry on the Proof Complexity of Random SatisfiabilitySymposium on Discrete Algorithms (SODA) 2021: 42–53

  [ ][ ][ URL ][ DOI ][ Download ]

•  

  Friedrich, Tobias; Neumann, Frank; Rothenberger, Ralf; Sutton, Andrew M.Solving Non-Uniform Planted and Filtered Random SAT Formulas GreedilyTheory and Applications of Satisfiability Testing (SAT) 2021: 188–206

  [ ][ ][ URL ][ DOI ][ Download ]

2020

•  

  Chauhan, Ankit; Friedrich, Tobias; Rothenberger, RalfGreed is Good for Deterministic Scale-Free NetworksAlgorithmica 2020: 3338–3389

  [ ][ ][ URL ][ DOI ][ Download ]

2019

•  

  Friedrich, Tobias; Krejca, Martin S.; Rothenberger, Ralf; Arndt, Tobias; Hafner, Danijar; Kellermeier, Thomas; Krogmann, Simon; Razmjou, ArminRouting for On-Street Parking Search using Probabilistic DataAI Communications 2019: 113–124

  [ ][ ][ URL ][ DOI ][ Download ]

•  

  Friedrich, Tobias; Göbel, Andreas; Neumann, Frank; Quinzan, Francesco; Rothenberger, RalfGreedy Maximization of Functions with Bounded Curvature Under Partition Matroid ConstraintsConference on Artificial Intelligence (AAAI) 2019: 2272–2279

  [ ][ ][ URL ][ DOI ][ Download ]

•  

  Peters, Jannik; Stephan, Daniel; Amon, Isabel; Gawendowicz, Hans; Lischeid, Julius; Salabarria, Julius; Umland, Jonas; Werner, Felix; Krejca, Martin S.; Rothenberger, Ralf; Kötzing, Timo; Friedrich, TobiasMixed Integer Programming versus Evolutionary Computation for Optimizing a Hard Real-World Staff Assignment ProblemInternational Conference on Automated Planning and Scheduling (ICAPS) 2019: 541–554

  [ ][ ][ URL ][ Download ]

•  

  Friedrich, Tobias; Rothenberger, RalfThe Satisfiability Threshold for Non-Uniform Random 2-SATInternational Colloquium on Automata, Languages and Programming (ICALP) 2019: 61:1–61:14

  [ ][ ][ URL ][ DOI ][ Download ]

•  

  Friedrich, Tobias; Rothenberger, RalfSharpness of the Satisfiability Threshold for Non-Uniform Random \(k\)-SAT.International Joint Conference on Artificial Intelligence (IJCAI) 2019: 6151–6155

  [ ][ ][ URL ][ DOI ][ Download ]

2018

•  

  Bläsius, Thomas; Eube, Jan; Feldtkeller, Thomas; Friedrich, Tobias; Krejca, Martin S.; Lagodzinski, J. A. Gregor; Rothenberger, Ralf; Severin, Julius; Sommer, Fabian; Trautmann, JustinMemory-restricted Routing With Tiled Map DataSystems, Man, and Cybernetics (SMC) 2018: 3347–3354

  [ ][ ][ DOI ][ Download ]

•  

  Friedrich, Tobias; Rothenberger, RalfSharpness of the Satisfiability Threshold for Non-Uniform Random k-SATTheory and Applications of Satisfiability Testing (SAT) 2018: 273–291

  Best Paper Award

  [ ][ ][ URL ][ DOI ][ Download ]

2017

•  

  Friedrich, Tobias; Krohmer, Anton; Rothenberger, Ralf; Sauerwald, Thomas; Sutton, Andrew M.Bounds on the Satisfiability Threshold for Power Law Distributed Random SATEuropean Symposium on Algorithms (ESA) 2017: 37:1–37:15

  [ ][ ][ URL ][ DOI ][ Download ]

•  

  Friedrich, Tobias; Krohmer, Anton; Rothenberger, Ralf; Sutton, Andrew M.Phase Transitions for Scale-Free SAT FormulasConference on Artificial Intelligence (AAAI) 2017: 3893–3899

  [ ][ ][ URL ][ Download ]

2016

•  

  Chauhan, Ankit; Friedrich, Tobias; Rothenberger, RalfGreed is Good for Deterministic Scale-Free NetworksFoundations of Software Technology and Theoretical Computer Science (FSTTCS) 2016: 33:1–33:15

  [ ][ ][ URL ][ DOI ][ Download ]

•  

  Arndt, Tobias; Hafner, Danijar; Kellermeier, Thomas; Krogmann, Simon; Razmjou, Armin; Krejca, Martin S.; Rothenberger, Ralf; Friedrich, TobiasProbabilistic Routing for On-Street Parking SearchEuropean Symposium on Algorithms (ESA) 2016: 6:1–6:13

  [ ][ ][ DOI ][ Download ]

2015

•  

  Rothenberger, Ralf; Grau, Sascha; Rossberg, MichaelDominating an s-t-Cut in a NetworkCurrent Trends in Theory and Practice of Computer Science (SOFSEM) 2015: 401–411

  [ ][ ][ URL ][ DOI ][ Download ]

•  

  Bringmann, Karl; Friedrich, Tobias; Hoefer, Martin; Rothenberger, Ralf; Sauerwald, ThomasUltra-Fast Load Balancing on Scale-Free NetworksInternational Colloquium on Automata, Languages and Programming (ICALP) 2015: 516–527

  [ ][ ][ DOI ][ Download ]