- Institute of Operating Systems and Computer Networks
- News
- About us
- Connected and Mobile Systems
- Distributed Systems
- Algorithms
- Microprocessor Lab
- Education
- Services
- Spin-Offs
- Research Cooperations
Institute of Operating Systems and Computer Networks
Mühlenpfordtstraße 23, 3rd floor
38106 Braunschweig
Room 317
+49 531 3913112
+49 531 3913109
krupke[[at]]ibr.cs.tu-bs.de
krupke.cc|GitHub| Google Scholar
I am interested in most aspects of algorithms and data structures, but my expertise lies in optimizing difficult, i.e., NP-hard, combinatorial problems with various techniques. My dissertation showcases large parts of my toolkit, including Mixed Integer Programming (Gurobi and CPLEX), Constraint Programming (CP-SAT of Google’s ortools), SAT-solvers, Dynamic Programming, Graph Algorithms, Approximation Algorithms, Reinforcement Learning, Meta-Heuristics, etc. There is a large overlap with the fields of Operations Research and Mathematical Optimization, but I prefer the term Algorithm Engineering as I am really focused on the algorithms and have primarily been educated by theoretical computer scientists. Thus, I am not just interested in just applying and combining these tools but also to understand how and why they work so well (or don’t). Currently, I am especially fascinated by CP-SAT because it smartly combines a lot of techniques, some of which seem unwise on first sight but work surprisingly well.My preferred programming languages are Python and C++ (if Python is too slow or if I want to play with low level stuff).
Outside the university, I like to test and expand my physical limits in weight lifting (currently at 2.2x own body weight in DL, aiming for 2.5x until the end of 2022) and Krav Maga. My preferred means of transport have two wheels (cyclocross bicycle and motorcycles).
Projects
- CheckMyTex and flachtex emerged from the need to proofread my dissertation.
- slurminade a decorator-based helper for distributing Python with Slurm.
- AeMeasure a database for macro-benchmarks of algorithms (to be used with slurminade).
- Using and Understanding ortools' CP-SAT: A Primer and Cheat Sheet
- ASIMOV ("Automated conStellatIon Management Of space Vehicles") for the European Space Agency (ESA) in cooperation with IRAS and Planet.com
- Multiple projects for Volkswagen
- CG:SHOP Challenges Co-organizer and technical lead for the CG:SHOP challenges.
- Robust: Project on disease module mining using Steiner trees (bioinformatics).
- ...
Teaching
Phillip Keldenich and I offer the new course algorithm engineering, which teaches you how to implement algorithms efficiently (lots of CPU and memory architecture) and to understand and use techniques for solving NP-hard optimization problems (MIP, CP, SAT, Heuristics). The course is aimed for master students and was first taught during summer term in 2022.
I assisted lectures in mathematical optimization, algorithm engineering, and approximation algorithms. Additionally, I supervised multiple software development labs, projects, and theses for students.
Achievements and Awards
- Best Paper Award at CIAC 2019 in Rome. Sponsored by Springer with 1000Euro
- Preis der Gesellschaft für Informatiker e.V. für herausragende Studienleistungen im Masterstudiengang Informatik (2017)
- Solved Problem 53 of The Open Problems Project in my Master's thesis (paper).
- Preis der Gesellschaft für Informatiker e.V. für herausragende Studienleistungen im Bachelorstudiengang Informatik (2014)
- Disproved a conjecture of Erik D. Demaine together with Maximilian Ernestus.
Curriculum Vitae
- Now: Post-doc at the Institute for Operating Systems and Computer Networks, Algorithmic Department
- Dec. 2016 - March 2022: Doctoral studies (Dr. rer. nat.) with dissertation 'Algorithm Engineering for Hard Problems in Computational Geometry' (supervised by Sándor Fekete, reviewed by Bill Cook and Joe Mitchell). Grade: 'Summa cum laude'
- Oct. 2014 - Nov. 2016: Master studies in Computer Science at the University of Technology in Brunswick, Germany. Grade: 1.0 'with honors'
- Oct. 2011 - Sept. 2014: Bachelor studies in Computer Science at the University of Technology in Brunswick, Germany. Grade: 1.2 'with honors'
Publications
Judith Bernett, Dominik Krupke, Sepideh Sadegh, Jan Baumbach, Sándor P. Fekete, Tim Kacprowski, Markus List, David B. Blumenthal
Robust disease module mining via enumeration of diverse prize-collecting Steiner trees [URL] [DOI]
2022, Bioinformatics, Volume: , pp.
Sándor P. Fekete, Linda Kleist, Dominik Krupke
Minimum Scan Cover with Angular Transition Costs [URL] [DOI]
2021, SIAM J. Discret. Math., Volume: 35, pp. 1337--1355
Kevin Buchin, Sándor P. Fekete, Alexander Hill, Linda Kleist, Irina Kostitsyna, Dominik Krupke, Roel Lambers, Martijn Struijs
Minimum Scan Cover and Variants - Theory and Experiments [URL] [DOI]
2021, 19th International Symposium on Experimental Algorithms, SEA 2021, June 7-9, 2021, Nice, France, Volume: 190, pp. 4:1--4:16
Mohamed Ben Larbi, Kattia Pozo, Tom Haylok, Mirue Choi, Benjamin Grzesik, Andreas Haas, Dominik Krupke, Harald Konstanski, Volker Schaus, Sándor Fekete, Christian Schurig, Enrico Stoll
Towards the Automated Operations of Large Distributed Satellite Systems. Part 1: Review and Paradigm Shifts [DOI]
2020, Advances in Space Research, Volume: 67, pp.
Mohamed Ben Larbi, Kattia Pozo, Mirue Choi, Tom Haylok, Benjamin Grzesik, Andreas Haas, Dominik Krupke, Harald Konstanski, Volker Schaus, Sándor Fekete, Christian Schurig, Enrico Stoll
Towards the Automated Operations of Large Distributed Satellite Systems. Part 2: Classifications and Tools [DOI]
2020, Advances in Space Research, Volume: 67, pp.
Aaron T. Becker, Sándor P. Fekete, Phillip Keldenich, Dominik Krupke, Christian Rieck, Christian Scheffer, Arne Schmidt
Tilt Assembly: Algorithms for Micro-factories That Build Objects with Uniform External Forces [URL] [DOI]
2020, Algorithmica, Volume: 82, pp. 165--187
Sándor P. Fekete, Linda Kleist, Dominik Krupke
Minimum Scan Cover with Angular Transition Costs [URL] [DOI]
2020, 36th International Symposium on Computational Geometry, SoCG 2020, June 23-26, 2020, Zürich, Switzerland, Volume: 164, pp. 43:1--43:18
Aaron T. Becker, Sándor P. Fekete, Li Huang, Phillip Keldenich, Linda Kleist, Dominik Krupke, Christian Rieck, Arne Schmidt
Targeted Drug Delivery: Algorithmic Methods for Collecting a Swarm of Particles with Uniform, External Forces [URL] [DOI]
2020, 2020 IEEE International Conference on Robotics and Automation, ICRA 2020, Paris, France, May 31 - August 31, 2020, pp. 2508--2514
Sándor P. Fekete, Alexander Hill, Dominik Krupke, Tyler Mayer, Joseph S. B. Mitchell, Ojas Parekh, Cynthia A. Phillips
Probing a Set of Trajectories to Maximize Captured Information [URL] [DOI]
2020, 18th International Symposium on Experimental Algorithms, SEA 2020, June 16-18, 2020, Catania, Italy, Volume: 160, pp. 5:1--5:14
Volker Schaus, Dominik Krupke, Mohamed Ben Larbi, Andreas Haas, Benjamin Grzesik, Jonas Radtke, Sándor Fekete, Enrico Stoll
Automated Constellation Management With Self-Regulating Data-Economic Actors
2019, 70th International Astronautical Congress (IAC)
Sándor P. Fekete, Dominik Krupke
Practical Methods for Computing Large Covering Tours and Cycle Covers with Turn Cost [URL] [DOI]
2019, Proceedings of the Twenty-First Workshop on Algorithm Engineering and Experiments, ALENEX 2019, San Diego, CA, USA, January 7-8, 2019, pp. 186--198
Dominik Krupke, Volker Schaus, Andreas Haas, Michael Perk, Jonas Dippel, Benjamin Grzesik, Mohamed Khalil Ben Larbi, Enrico Stoll, Tom Haylock, Harald Konstanski, Kattia Flores Pozo, Mirue Choi, Christian Schurig, Sándor P. Fekete
Automated Data Retrieval from Large-Scale Distributed Satellite Systems [URL] [DOI]
2019, 15th IEEE International Conference on Automation Science and Engineering, CASE 2019, Vancouver, BC, Canada, August 22-26, 2019, pp. 1789--1795
Sándor P. Fekete, Dominik Krupke
Covering Tours and Cycle Covers with Turn Costs: Hardness and Approximation [URL] [DOI]
2019, Algorithms and Complexity - 11th International Conference, CIAC 2019, Rome, Italy, May 27-29, 2019, Proceedings, Volume: 11485, pp. 224--236
An Nguyen, Dominik Krupke, Mary Burbage, Shriya Bhatnagar, Sándor P. Fekete, Aaron T. Becker
Using a UAV for Destructive Surveys of Mosquito Population [URL] [DOI]
2018, 2018 IEEE International Conference on Robotics and Automation, ICRA 2018, Brisbane, Australia, May 21-25, 2018, pp. 7812--7819
Phillip Keldenich, Sheryl Manzoor, Li Huang, Dominik Krupke, Arne Schmidt, Sándor P. Fekete, Aaron T. Becker
On Designing 2D Discrete Workspaces to Sort or Classify Polynminoes [URL] [DOI]
2018, 2018 IEEE/RSJ International Conference on Intelligent Robots and Systems, IROS 2018, Madrid, Spain, October 1-5, 2018, pp. 1--9
Sándor P. Fekete, Andreas Haas, Michael Hemmer, Michael Hoffmann, Irina Kostitsyna, Dominik Krupke, Florian Maurer, Joseph S. B. Mitchell, Arne Schmidt, Christiane Schmidt, Julian Troegel
Computing nonsimple polygons of minimum perimeter [URL] [DOI]
2017, J. Comput. Geom., Volume: 8, pp. 340--365
Aaron T. Becker, Mustapha Debboun, Sándor P. Fekete, Dominik Krupke, An Nguyen
Zapping Zika with a Mosquito-Managing Drone: Computing Optimal Flight Patterns with Minimum Turn Cost (Multimedia Contribution) [URL] [DOI]
2017, 33rd International Symposium on Computational Geometry, SoCG 2017, July 4-7, 2017, Brisbane, Australia, Volume: 77, pp. 62:1--62:5
Arun Mahadev, Dominik Krupke, Sándor P. Fekete, Aaron T. Becker
Mapping and coverage with a particle swarm controlled by uniform inputs [URL] [DOI]
2017, 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems, IROS 2017, Vancouver, BC, Canada, September 24-28, 2017, pp. 1097--1104
Aaron T. Becker, Sándor P. Fekete, Phillip Keldenich, Dominik Krupke, Christian Rieck, Christian Scheffer, Arne Schmidt
Tilt Assembly: Algorithms for Micro-Factories that Build Objects with Uniform External Forces [URL] [DOI]
2017, 28th International Symposium on Algorithms and Computation, ISAAC 2017, December 9-12, 2017, Phuket, Thailand, Volume: 92, pp. 11:1--11:13
Dominik Krupke
Algorithmic methods for complex dynamic sweeping problems [URL]
2016, Master Thesis
Arun V. Mahadev, Dominik Krupke, Jan-Marc Reinhardt, Sándor P. Fekete, Aaron T. Becker
Collecting a swarm in a grid environment using shared, global inputs [URL] [DOI]
2016, IEEE International Conference on Automation Science and Engineering, CASE 2016, Fort Worth, TX, USA, August 21-25, 2016, pp. 1231--1236
Sándor P. Fekete, Andreas Haas, Michael Hemmer, Michael Hoffmann, Irina Kostitsyna, Dominik Krupke, Florian Maurer, Joseph S. B. Mitchell, Arne Schmidt, Christiane Schmidt, Julian Troegel
Computing Nonsimple Polygons of Minimum Perimeter [URL] [DOI]
2016, Experimental Algorithms - 15th International Symposium, SEA 2016, St. Petersburg, Russia, June 5-8, 2016, Proceedings, Volume: 9685, pp. 134--149
Dominik Krupke, Maximilian Ernestus, Michael Hemmer, Sándor P. Fekete
Distributed cohesive control for robot swarms: Maintaining good connectivity in the presence of exterior forces [URL] [DOI]
2015, 2015 IEEE/RSJ International Conference on Intelligent Robots and Systems, IROS 2015, Hamburg, Germany, September 28 - October 2, 2015, pp. 413--420
Dominik Krupke, Michael Hemmer, James McLurkin, Yu Zhou, Sándor P. Fekete
A parallel distributed strategy for arraying a scattered robot swarm [URL] [DOI]
2015, 2015 IEEE/RSJ International Conference on Intelligent Robots and Systems, IROS 2015, Hamburg, Germany, September 28 - October 2, 2015, pp. 2795--2802
Maximilian Ernestus, Dominik Krupke
Distributed, scalable algorithmic methods for swarms with multiple leader robots [URL]
2014, Bachelor Thesis
Björn Bankowski, Thiemo Clausen, Dirk Ehmen, Maximilian Ernestus, Henning Hasemann, Tobias Jura, Alexander Kröller, Dominik Krupke, Marco Nikander
Panic Room: Experiencing Overload and Having Fun in the Process [URL] [DOI]
2014, Distributed, Ambient, and Pervasive Interactions - Second International Conference, DAPI 2014, Held as Part of HCI Interational 2014, Heraklion, Crete, Greece, June 22-27, 2014. Proceedings, Volume: 8530, pp. 241--252