# All publications in 2019

The following listing contains all publications of the current members of the Algorithm Engineering group in 2019.

You can view all publications of the current members of the Algorithm Engineering group. For other listings, please see:

- years: 2021, 2020, 2019, 2018, 2017, 2016, 2015, 2014, 2013, 2012, 2011, 2010
- researchers: Prof. Dr. Tobias Friedrich, Dr. Katrin Casel, Dr. Sarel Cohen, Dr. Ágnes Cseh, Dr. Andreas Göbel, Dr. Davis Issac, Dr. Timo Kötzing, Dr. Nikhil Kumar, Dr. Pascal Lenzner
- PhD students: Vanja Doskoč, Philipp Fischbeck, Maximilian Katzmann, Simon Krogmann, Gregor Lagodzinski, Anna Melnichenko, Louise Molitor, Stefan Neubert, Marcus Pappik, Francesco Quinzan, Ralf Rothenberger, Martin Schirneck, Karen Seidel, Christopher Weyand, Ziena Zeif
- theory conferences: ICALP, MFCS, SAGT, STACS, STOC, WINE

algorithm conferences: ALENEX, ESA, GD, ISAAC, SODA, SPAA, SWAT, WAW - artificial intelligence conferences: AAAI, AAMAS, ALT, COLT, ECAI, ICAPS, IJCAI, SAT

evolutionary computation conferences: CEC, EMO, EvoCOP, FOGA, GECCO, PPSN

## Conference Publications

2019

- 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 - Roostapour, Vahid; Neumann, Aneta; Neumann, Frank; Friedrich, Tobias
**Pareto Optimization for Subset Selection with Dynamic Cost Constraints**. Conference on Artificial Intelligence (AAAI) 2019: 2354–2361 - Feldotto, Matthias; Lenzner, Pascal; Molitor, Louise; Skopalik, Alexander
**From Hotelling to Load Balancing: Approximation and the Principle of Minimum Differentiation**. Autonomous Agents and Multiagent Systems (AAMAS) 2019: 1949–1951 - Bläsius, Thomas; Friedrich, Tobias; Lischeid, Julius; Meeks, Kitty; Schirneck, Martin
**Efficiently Enumerating Hitting Sets of Hypergraphs Arising in Data Profiling**. Algorithm Engineering and Experiments (ALENEX) 2019: 130–143 - Fokina, Ekaterina; Kötzing, Timo; San Mauro, Luca
**Limit Learning Equivalence Structures**. Algorithmic Learning Theory (ALT) 2019: 383–403 - Casel, Katrin; Fernau, Henning; Khosravian Ghadikolaei, Mehdi; Monnot, Jerome; Sikora, Florian
**Extension of vertex cover and independent set in some classes of graphs and generalizations**. International Conference on Algorithms and Complexity (CIAC) 2019: 124–136 - Bläsius, Thomas; Friedrich, Tobias; Katzmann, Maximilian; Meyer, Ulrich; Penschuck, Manuel; Weyand, Christopher
**Efficiently Generating Geometric Inhomogeneous and Hyperbolic Random Graphs**. European Symposium on Algorithms (ESA) 2019: 21:2–21:14EATCS Best Paper Award - Casel, Katrin; Fernau, Henning; Khosravian Ghadikolaei, Mehdi; Monnot, Jerome; Sikora, Florian
**Extension of some edge graph problems: standard and parameterized complexity**. Fundamentals of Computation Theory (FCT) 2019: 185–200 - Doerr, Benjamin; Kötzing, Timo
**Multiplicative Up-Drift**. Genetic and Evolutionary Computation Conference (GECCO) 2019 - Alon, Noga; Chechik, Shiri; Cohen, Sarel
**Deterministic Combinatorial Replacement Paths and Distance Sensitivity Oracles**. International Colloquium on Automata, Languages and Programming (ICALP) 2019: 12:1–12:14 - 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 - Casel, Katrin; Day, Joel D.; Fleischmann, Pamela; Kociumaka, Tomasz; Manea, Florin; Schmid, Markus L.
**Graph and String Parameters: Connections Between Pathwidth, Cutwidth and the Locality Number**. International Colloquium on Automata, Languages and Programming (ICALP) 2019: 109:1–109:16 - 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 - 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 - Gao, Ziyuan; Jain, Sanjay; Khoussainov, Bakhadyr; Li, Wei; Melnikov, Alexander; Seidel, Karen; Stephan, Frank
**Random Subgroups of Rationals**. Mathematical Foundations of Computer Science (MFCS) 2019: 25:1–25:14 - Chechik, Shiri; Cohen, Sarel
**Near Optimal Algorithms For The Single Source Replacement Paths Problem**. Symposium on Discrete Algorithms (SODA) 2019: 2090–2109 - Bilò, Davide; Friedrich, Tobias; Lenzner, Pascal; Melnichenko, Anna
**Geometric Network Creation Games**. Symposium on Parallelism in Algorithms and Architectures (SPAA) 2019: 323–332 - Friedrich, Tobias
**From Graph Theory to Network Science: The Natural Emergence of Hyperbolicity**. Symposium Theoretical Aspects of Computer Science (STACS) 2019: 5:1–5:9 - Cseh, Ágnes; Juhos, Attila
**Pairwise Preferences in the Stable Marriage Problem**. Symposium Theoretical Aspects of Computer Science (STACS) 2019: 21:1–21:16 - Bläsius, Thomas; Friedrich, Tobias; Sutton, Andrew M.
**On the Empirical Time Complexity of Scale-Free 3-SAT at the Phase Transition**. Tools and Algorithms for the Construction and Analysis of Systems (TACAS) 2019: 117–134 - Bläsius, Thomas; Fischbeck, Philipp; Friedrich, Tobias; Schirneck, Martin
**Understanding the Effectiveness of Data Reduction in Public Transportation Networks**. Workshop on Algorithms and Models for the Web Graph (WAW) 2019: 87–101 - Echzell, Hagen; Friedrich, Tobias; Lenzner, Pascal; Molitor, Louise; Pappik, Marcus; Schöne, Friedrich; Sommer, Fabian; Stangl, David
**Convergence and Hardness of Strategic Schelling Segregation**. Web and Internet Economics (WINE) 2019: 156–170

## Journal Publications

2019

- Issac, Davis; Chandran, L. Sunil; Zhou, Sanming
**Hadwiger’s conjecture for squares of 2-trees**. European Journal of Combinatorics 2019: 159–174 - 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 - Doerr, Benjamin; Doerr, Carola; Kötzing, Timo
**Solving Problems with Unknown Solution Length at Almost No Extra Cost**. Algorithmica 2019: 703–748 - Shi, Feng; Schirneck, Martin; Friedrich, Tobias; Kötzing, Timo; Neumann, Frank
**Reoptimization Time Analysis of Evolutionary Algorithms on Linear Functions Under Dynamic Uniform Constraints**. Algorithmica 2019: 828–857 - Doerr, Benjamin; Fischbeck, Philipp; Frahnow, Clemens; Friedrich, Tobias; Kötzing, Timo; Schirneck, Martin
**Island Models Meet Rumor Spreading**. Algorithmica 2019: 886–915 - Cseh, Ágnes; Matuschke, Jannik
**New and Simple Algorithms for Stable Flow Problems**. Algorithmica 2019: 2557–2591 - Neumann, Aneta; Neumann, Frank; Friedrich, Tobias
**Quasi-random Image Transition and Animation**. Australian Journal of Intelligent Information Processing Systems 2019: 10–18 - Cechlárová, Katarína; Cseh, Ágnes; Manlove, David
**Selected open problems in Matching Under Preferences**. Bulletin of the European Association for Theoretical Computer Science 2019: 14–38 - Battaglia, Francesco; Cucina, Domenico; Rizzo, Manuel
**Detection and estimation of additive outliers in seasonal time series**. Computational Statistics 2019: 1–17 - Trubenova, Barbora; Kötzing, Timo; Krejca, Martin S.; Lehre, Per Kristian
**Surfing on the seascape: Adaptation in a changing environment**. Evolution: International Journal of Organic Evolution 2019: 1356–1374 - Bläsius, Thomas; Rademacher, Marcel; Rutter, Ignaz
**How to Draw a Planarization**. Graph Algorithms and Applications 2019: 653–682 - Cseh, Ágnes; Skutella, Martin
**Paths to stable allocations**. International Journal of Game Theory 2019: 835–862 - Cucina, Domenico; Rizzo, Manuel; Ursu, Eugen
**Multiple changepoint detection for periodic autoregressive models with an application to river flow analysis**. Stochastic Environmental Research and Risk Assessment 2019: 1137–1157 - Batra, Sanjit Singh; Kumar, Nikhil; Tripathi, Amitabha
**Some Problems Concerning the Frobenius Number for Extensions of an Arithmetic Progression**. The Ramanujan Journal 2019: 545–565 - Friedrich, Tobias; Kötzing, Timo; Krejca, Martin S.
**Unbiasedness of Estimation-of-Distribution Algorithms**. Theoretical Computer Science 2019: 46–59 - Kötzing, Timo; Krejca, Martin S.
**First-hitting times under drift**. Theoretical Computer Science 2019: 51–69 - Cseh, Ágnes; Irving, Robert W.; Manlove, David F.
**The Stable Roommates Problem with Short Lists**. Theory of Computing Systems 2019: 128–149 - 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 - Roostapour, Vahid; Neumann, Aneta; Neumann, Frank; Friedrich, Tobias
**Pareto Optimization for Subset Selection with Dynamic Cost Constraints**. Conference on Artificial Intelligence (AAAI) 2019: 2354–2361 - Feldotto, Matthias; Lenzner, Pascal; Molitor, Louise; Skopalik, Alexander
**From Hotelling to Load Balancing: Approximation and the Principle of Minimum Differentiation**. Autonomous Agents and Multiagent Systems (AAMAS) 2019: 1949–1951 - Bläsius, Thomas; Friedrich, Tobias; Lischeid, Julius; Meeks, Kitty; Schirneck, Martin
**Efficiently Enumerating Hitting Sets of Hypergraphs Arising in Data Profiling**. Algorithm Engineering and Experiments (ALENEX) 2019: 130–143 - Fokina, Ekaterina; Kötzing, Timo; San Mauro, Luca
**Limit Learning Equivalence Structures**. Algorithmic Learning Theory (ALT) 2019: 383–403 - Casel, Katrin; Fernau, Henning; Khosravian Ghadikolaei, Mehdi; Monnot, Jerome; Sikora, Florian
**Extension of vertex cover and independent set in some classes of graphs and generalizations**. International Conference on Algorithms and Complexity (CIAC) 2019: 124–136 - Bläsius, Thomas; Friedrich, Tobias; Katzmann, Maximilian; Meyer, Ulrich; Penschuck, Manuel; Weyand, Christopher
**Efficiently Generating Geometric Inhomogeneous and Hyperbolic Random Graphs**. European Symposium on Algorithms (ESA) 2019: 21:2–21:14EATCS Best Paper Award - Casel, Katrin; Fernau, Henning; Khosravian Ghadikolaei, Mehdi; Monnot, Jerome; Sikora, Florian
**Extension of some edge graph problems: standard and parameterized complexity**. Fundamentals of Computation Theory (FCT) 2019: 185–200 - Doerr, Benjamin; Kötzing, Timo
**Multiplicative Up-Drift**. Genetic and Evolutionary Computation Conference (GECCO) 2019 - Alon, Noga; Chechik, Shiri; Cohen, Sarel
**Deterministic Combinatorial Replacement Paths and Distance Sensitivity Oracles**. International Colloquium on Automata, Languages and Programming (ICALP) 2019: 12:1–12:14 - 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 - Casel, Katrin; Day, Joel D.; Fleischmann, Pamela; Kociumaka, Tomasz; Manea, Florin; Schmid, Markus L.
**Graph and String Parameters: Connections Between Pathwidth, Cutwidth and the Locality Number**. International Colloquium on Automata, Languages and Programming (ICALP) 2019: 109:1–109:16 - 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 - 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 - Gao, Ziyuan; Jain, Sanjay; Khoussainov, Bakhadyr; Li, Wei; Melnikov, Alexander; Seidel, Karen; Stephan, Frank
**Random Subgroups of Rationals**. Mathematical Foundations of Computer Science (MFCS) 2019: 25:1–25:14 - Chechik, Shiri; Cohen, Sarel
**Near Optimal Algorithms For The Single Source Replacement Paths Problem**. Symposium on Discrete Algorithms (SODA) 2019: 2090–2109 - Bilò, Davide; Friedrich, Tobias; Lenzner, Pascal; Melnichenko, Anna
**Geometric Network Creation Games**. Symposium on Parallelism in Algorithms and Architectures (SPAA) 2019: 323–332 - Friedrich, Tobias
**From Graph Theory to Network Science: The Natural Emergence of Hyperbolicity**. Symposium Theoretical Aspects of Computer Science (STACS) 2019: 5:1–5:9 - Cseh, Ágnes; Juhos, Attila
**Pairwise Preferences in the Stable Marriage Problem**. Symposium Theoretical Aspects of Computer Science (STACS) 2019: 21:1–21:16 - Bläsius, Thomas; Friedrich, Tobias; Sutton, Andrew M.
**On the Empirical Time Complexity of Scale-Free 3-SAT at the Phase Transition**. Tools and Algorithms for the Construction and Analysis of Systems (TACAS) 2019: 117–134 - Bläsius, Thomas; Fischbeck, Philipp; Friedrich, Tobias; Schirneck, Martin
**Understanding the Effectiveness of Data Reduction in Public Transportation Networks**. Workshop on Algorithms and Models for the Web Graph (WAW) 2019: 87–101 - Echzell, Hagen; Friedrich, Tobias; Lenzner, Pascal; Molitor, Louise; Pappik, Marcus; Schöne, Friedrich; Sommer, Fabian; Stangl, David
**Convergence and Hardness of Strategic Schelling Segregation**. Web and Internet Economics (WINE) 2019: 156–170 - Krejca, Martin S.
**Theoretical Analyses of Univariate Estimation-of-Distribution Algorithms**. PhD thesis, Hasso Plattner Institute, University of Potsdam 2019ACM SIGEVO Dissertation Award, Honorable Mention **FOGA ’19: Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms**. ACM 2019Editorship**Theory of Randomized Optimization Heuristics**. Dagstuhl Reports 2019: 61–94