Hasso-Plattner-Institut
Prof. Dr. Tobias Friedrich
  
 

Ralf Rothenberger

Chair for Algorithm Engineering
Hasso Plattner Institute

Office: A-1.13
Tel: +49 331 5509-417
E-Mail: Ralf.Rothenberger(at)hpi.de
 

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

  • algorithms

    • random algorithms
    • load balancing

Teaching

As Advisor

 

Activities

I am co-organizing our weekly Research Seminar. Also, I am a member of the HPI's Research School on "Service-Oriented Systems Engineering".

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

Past Activities:

 

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

[ 2019 ] [ 2018 ] [ 2017 ] [ 2016 ] [ 2015 ]

2019 [ to top ]

  • Friedrich, Tobias; Rothenberger, Ralf Sharpness of the Satisfiability Threshold for Non-Uniform Random k-SAT. International Joint Conference on Artificial Intelligence (IJCAI) 2019: 6151-6155
    Extended abstract
     
  • The Satisfiability Thresh... - Download
    Friedrich, Tobias; Rothenberger, Ralf The Satisfiability Threshold for Non-Uniform Random 2-SAT. International Colloquium on Automata, Languages and Programming (ICALP) 2019: 61:1-61:14
     
  • Mixed Integer Programming... - 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, Tobias Mixed Integer Programming versus Evolutionary Computation for Optimizing a Hard Real-World Staff Assignment Problem. International Conference on Automated Planning and Scheduling (ICAPS) 2019: 541-554
     
  • Routing for On-Street Par... - Download
    Friedrich, Tobias; Krejca, Martin S.; Rothenberger, Ralf; Arndt, Tobias; Hafner, Danijar; Kellermeier, Thomas; Krogmann, Simon; Razmjou, Armin Routing for On-Street Parking Search using Probabilistic Data. AI Communications 2019: 113-124
     
  • Greedy Maximization of Fu... - Download
    Friedrich, Tobias; Göbel, Andreas; Neumann, Frank; Quinzan, Francesco; Rothenberger, Ralf Greedy Maximization of Functions with Bounded Curvature Under Partition Matroid Constraints. Conference on Artificial Intelligence (AAAI) 2019: 2272-2279
     

2018 [ to top ]

  • Memory-restricted Routing... - Download
    Bläsius, Thomas; Eube, Jan; Feldtkeller, Thomas; Friedrich, Tobias; Krejca, Martin S.; Lagodzinski, J. A. Gregor; Rothenberger, Ralf; Severin, Julius; Sommer, Fabian; Trautmann, Justin Memory-restricted Routing With Tiled Map Data. IEEE International Conference on Systems, Man, and Cybernetics (SMC) 2018: 3347-3354
     
  • Sharpness of the Satisfia... - Download
    Friedrich, Tobias; Rothenberger, Ralf Sharpness of the Satisfiability Threshold for Non-Uniform Random k-SAT. Theory and Applications of Satisfiability Testing (SAT) 2018: 273--291
    Best Paper Award
     

2017 [ to top ]

  • Bounds on the Satisfiabil... - Download
    Friedrich, Tobias; Krohmer, Anton; Rothenberger, Ralf; Sauerwald, Thomas; Sutton, Andrew M. Bounds on the Satisfiability Threshold for Power Law Distributed Random SAT. European Symposium on Algorithms (ESA) 2017: 37:1-37:15
     
  • Phase Transitions for Sca... - Download
    Friedrich, Tobias; Krohmer, Anton; Rothenberger, Ralf; Sutton, Andrew M. Phase Transitions for Scale-Free SAT Formulas. Conference on Artificial Intelligence (AAAI) 2017: 3893-3899
     

2016 [ to top ]

  • Greed is Good for Determi... - Download
    Chauhan, Ankit; Friedrich, Tobias; Rothenberger, Ralf Greed is Good for Deterministic Scale-Free Networks. Foundations of Software Technology and Theoretical Computer Science (FSTTCS) 2016: 33:1-33:15
     
  • Probabilistic Routing for... - Download
    Arndt, Tobias; Hafner, Danijar; Kellermeier, Thomas; Krogmann, Simon; Razmjou, Armin; Krejca, Martin S.; Rothenberger, Ralf; Friedrich, Tobias Probabilistic Routing for On-Street Parking Search. European Symposium on Algorithms (ESA) 2016: 6:1-6:13
     

2015 [ to top ]

  • Dominating an s-t-Cut in ... - Download
    Rothenberger, Ralf; Grau, Sascha; Rossberg, Michael Dominating an s-t-Cut in a Network. Current Trends in Theory and Practice of Computer Science (SOFSEM) 2015: 401-411
     
  • Ultra-Fast Load Balancing... - Download
    Bringmann, Karl; Friedrich, Tobias; Hoefer, Martin; Rothenberger, Ralf; Sauerwald, Thomas Ultra-Fast Load Balancing on Scale-Free Networks. International Colloquium on Automata, Languages and Programming (ICALP) 2015: 516-527