# All Publications in 2020

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

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

- years: 2024, 2023, 2022, 2021, 2020, 2019, 2018, 2017, 2016, 2015, 2014, 2013, 2012, 2011, 2010
- researchers: Prof. Dr. Tobias Friedrich, Dr. Samuel Baguley, Dr. Sarel Cohen, Dr. Andreas Göbel, Dr. Timo Kötzing, Dr. Pascal Lenzner, Dr. Kirill Simonov, Dr. George Skretas, Dr. Shaily Verma
- PhD students: Panagiotis Aivasiliotis, Michelle Döring, Philipp Fischbeck, Hans Gawendowicz, Merlin de la Haye, Nicolas Klodt, Simon Krogmann, Xiaoyue Sherry Li, Paraskevi Machaira,Nadym Mallek, Stefan Neubert, Aikaterini Niklanovits, Marcus Pappik, Aishwarya Radhakrishnan, Janosch Ruff, Farehe Soheil, Ziena Zeif
- theory conferences: FOCS, 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

2020

- Cseh, Ágnes; Fleiner, Tamás
**The Complexity of Cake Cutting with Unequal Shares**ACM Transactions on Algorithms 2020: 1–21 - Shi, Feng; Schirneck, Martin; Friedrich, Tobias; Kötzing, Timo; Neumann, Frank
**Correction to: Reoptimization Time Analysis of Evolutionary Algorithms on Linear Functions Under Dynamic Uniform Constraints**Algorithmica 2020: 3117–3123 - Chauhan, Ankit; Friedrich, Tobias; Rothenberger, Ralf
**Greed is Good for Deterministic Scale-Free Networks**Algorithmica 2020: 3338–3389 - Ghorbani, Ebrahim; Haemers, Willem H.; Reza Maimani, Hamid; Parsaei Majd, Leila
**On sign-symmetric signed graphs**Ars Mathematica Contemporane 2020: 83–93 - Casel, Katrin; Dreier, Jan; Fernau, Henning; Gobbert, Moritz; Kuinke, Philipp; Sanchez Villaamil, Fernando; Schmid, Markus L.; van Leeuwen, Erik Jan
**Complexity of independency and cliquy trees**Discrete Applied Mathematics 2020: 2–15 - Bazgan, Cristina; Brankovic, Ljiljana; Casel, Katrin; Fernau, Henning
**Domination chain: Characterisation, classical complexity, parameterised complexity and approximability**Discrete Applied Mathematics 2020: 23–42 - Akbari, Saieed; Reza Maimani, Hamid; Parsaei Majd, Leila; Wanless, Ian M.
**Zero-sum flows for Steiner systems**Discrete Mathematics 2020: 112074 - Cseh, Ágnes; Heeger, Klaus
**The stable marriage problem with ties and restricted edges**Discrete Optimization 2020: 100571 - Doerr, Benjamin; Krejca, Martin S.
**Significance-based Estimation-of-Distribution Algorithms**IEEE Transactions on Evolutionary Computation 2020: 1025–1034 - Alizadeh, Faezeh; Maimani, Hamid Reza; Parsaei Majd, Leila; Rajabi Parsa, Mina
**Roman {2}-domination in graphs and graph products**Iranian Journal of Mathematical Sciences and Informatics Iranian Journal of Mathematical Sciences and Informatics 2020 - Bläsius, Thomas; Friedrich, Tobias; Katzmann, Maximilian; Krohmer, Anton
**Hyperbolic Embeddings for Near-Optimal Greedy Routing**Journal of Experimental Algorithmics (JEA) 2020: 1–18 - Birnick, Johann; Bläsius, Thomas; Friedrich, Tobias; Naumann, Felix; Papenbrock, Thorsten; Schirneck, Martin
**Hitting Set Enumeration with Partial Information for Unique Column Combination Discovery**Proceedings of the VLDB Endowment 2020: 2270–2283 - Battaglia, Francesco; Cucina, Domenico; Rizzo, Manuel
**Parsimonious periodic autoregressive models for time series with evolving trend and seasonality**Statistics and Computing 2020: 77–91 - Friedrich, Tobias; Kötzing, Timo; Lagodzinski, J. A. Gregor; Neumann, Frank; Schirneck, Martin
**Analysis of the (1+1) EA on Subclasses of Linear Functions under Uniform and Linear Constraints**Theoretical Computer Science 2020: 3–19 - Kötzing, Timo; Lagodzinski, J. A. Gregor; Lengler, Johannes; Melnichenko, Anna
**Destructiveness of lexicographic parsimony pressure and alleviation by a concatenation crossover in genetic programming**Theoretical Computer Science 2020: 96–113 - Krejca, Martin S.; Witt, Carsten
**Lower Bounds on the Run Time of the Univariate Marginal Distribution Algorithm on OneMax**Theoretical Computer Science 2020: 143–165 - Doerr, Benjamin; Kötzing, Timo; Lagodzinski, J. A. Gregor; Lengler, Johannes
**The impact of lexicographic parsimony pressure for ORDER/MAJORITY on the run time**Theoretical Computer Science 2020: 144–168 - Bil{ò}, Davide; Lenzner, Pascal
**On the Tree Conjecture for the Network Creation Game**Theory of Computing Systems 2020: 422–443 - Krejca, Martin S.; Witt, Carsten
**Theory of Estimation-of-Distribution Algorithms**Theory of Evolutionary Computation: Recent Developments in Discrete Optimization 2020: 405–442 - Doskoč, Vanja; Kötzing, Timo
**Cautious Limit Learning**Algorithmic Learning Theory (ALT) 2020: 251–276 - Das, Syamantak; Jain, Lavina; Kumar, Nikhil
**A Constant Factor Approximation for Capacitated Min-Max Tree Cover**Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM) 2020: 55:1–55:13 - Bläsius, Thomas; Böther, Maximilian; Fischbeck, Philipp; Friedrich, Tobias; Gries, Alina; Hüffner, Falk; Kißig, Otto; Lenzner, Pascal; Molitor, Louise; Schiller, Leon; Wells, Armin; Wietheger, Simon
**A Strategic Routing Framework and Algorithms for Computing Alternative Paths**Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS) 2020: 10:1–10:14 - Fogel, Sharon; Averbuch-Elor, Hadar; Cohen, Sarel; Mazor, Shai; Litman, Roee
**ScrabbleGAN: Semi-Supervised Varying Length Handwritten Text Generation**Conference on Computer Vision and Pattern Recognition (CVPR) 2020: 4323–4332 - Doskoč, Vanja; Friedrich, Tobias; Göbel, Andreas; Neumann, Aneta; Neumann, Frank; Quinzan, Francesco
**Non-Monotone Submodular Maximization with Multiple Knapsacks in Static and Dynamic Settings**European Conference on Artificial Intelligence (ECAI) 2020: 435–442 - Bläsius, Thomas; Friedrich, Tobias; Schirneck, Martin
**The Minimization of Random Hypergraphs**European Symposium on Algorithms (ESA) 2020: 21:1–21:15 - Garg, Naveen; Kumar, Nikhil
**Dual Half-Integrality for Uncrossable Cut Cover and Its Application to Maximum Half-Integral Flow**European Symposium on Algorithms (ESA) 2020: 55:1–55:13 - Doerr, Benjamin; Krejca, Martin S.
**The Univariate Marginal Distribution Algorithm Copes Well with Deception and Epistasis**Evolutionary Computation in Combinatorial Optimization (EvoCOP) 2020: 51–66Best-Paper Award - Bilò, Davide; Friedrich, Tobias; Lenzner, Pascal; Melnichenko, Anna; Molitor, Louise
**Fair Tree Connection Games with Topology-Dependent Edge Cost**Foundations of Software Technology and Theoretical Computer Science (FSTTCS) 2020: 15:1–15:15 - Doerr, Benjamin; Krejca, Martin S.
**Bivariate Estimation-of-Distribution Algorithms Can Find an Exponential Number of Optima**Genetic and Evolutionary Computation Conference (GECCO) 2020: 796–804 - Bossek, Jakob; Casel, Katrin; Kerschke, Pascal; Neumann, Frank
**The Node Weight Dependent Traveling Salesperson Problem: Approximation Algorithms and Randomized Search Heuristics**Genetic and Evolutionary Computation Conference (GECCO) 2020: 1286–1294 - Friedrich, Tobias; Krejca, Martin S.; Lagodzinski, J. A. Gregor; Rizzo, Manuel; Zahn, Arthur
**Memetic Genetic Algorithms for Time Series Compression by Piecewise Linear Approximation**International Conference on Neural Information Processing (ICONIP) 2020: 592–604 - Echzell, Hagen; Friedrich, Tobias; Lenzner, Pascal; Melnichenko, Anna
**Flow-Based Network Creation Games**International Joint Conference on Artificial Intelligence (IJCAI) 2020: 139–145 - Garg, Naveen; Kumar, Nikhil; Sebö, András
**Integer Plane Multiflow Maximisation: Flow-Cut Gap and One-Quarter-Approximation**Integer Programming and Combinatorial Optimization (IPCO) 2020: 144–157 - Feldmann, Andreas; Issac, Davis; Rai, Ashutosh
**Fixed-Parameter Tractability of the Weighted Edge Clique Partition Problem**International Symposium on Parameterized and Exact Computation (IPEC) 2020: 1–16 - Kumar, Nikhil
**Multicommodity Flows in Planar Graphs with Demands on Faces**International Symposium on Algorithms and Computation (ISAAC) 2020: 1–11 - Bilò, Davide; Bilò, Vittorio; Lenzner, Pascal; Molitor, Louise
**Topological Influence and Locality in Swap Schelling Games**International Symposium on Mathematical Foundations of Computer Science (MFCS) 2020: 15:1–15:15 - Michail, Othon; Skretas, George; Spirakis, G. Paul
**Distributed Computation and Reconfiguration in Actively Dynamic Networks**Principles of Distributed Computing (PODC) 2020: 448–457 - Kötzing, Timo; Witt, Carsten
**Improved Fixed-Budget Results via Drift Analysis**Parallel Problem Solving From Nature (PPSN) 2020: 648–660 - Antoniadis, Antonios; Garg, Naveen; Kumar, Gunjan; Kumar, Nikhil
**Parallel Machine Scheduling to Minimize Energy Consumption**Symposium on Discrete Algorithms (SODA) 2020: 2758–2769 - Feldmann, Michael; Khazraei, Ardalan; Scheideler, Christian
**Time- and Space-Optimal Clock Synchronization in the Beeping Model**Symposium Parallelism in Algorithms and Architectures (SPAA) 2020: 223–233 - Bläsius, Thomas; Fischbeck, Philipp; Friedrich, Tobias; Katzmann, Maximilian
**Solving Vertex Cover in Polynomial Time on Hyperbolic Random Graphs**Symposium on the Theoretical Aspects of Computer Science (STACS) 2020: 25:1–25:14 - Chechik, Shiri; Cohen, Sarel
**Distance sensitivity oracles with subcubic preprocessing time and fast query time**Symposium Theory of Computing (STOC) 2020: 1375–1388 - Becher, Kilian; Lagodzinski, J. A. Gregor; Strufe, Thorsten
**Privacy-Preserving Public Verification of Ethical Cobalt Sourcing**Trust, Security and Privacy in Computing and Communications (TrustCom) 2020: 998–1005 - Held, Stephan; Khazraei, Ardalan
**An Improved Approximation Algorithm for the Uniform Cost-Distance Steiner Tree Problem**Workshop on Approximation and Online Algorithms (WAOA) 2020: 189–203 - Khazraei, Ardalan; Kötzing, Timo; Seidel, Karen
**Learning Half-Spaces and other Concept Classes in the Limit with Iterative Learners**CoRR 2020ArXiv preprint - Kötzing, Timo; Seidel, Karen
**Learning Languages in the Limit from Positive Information with Finitely Many Memory Changes**CoRR 2020ArXiv preprint

## Journal Publications

2020

- Cseh, Ágnes; Fleiner, Tamás
**The Complexity of Cake Cutting with Unequal Shares**ACM Transactions on Algorithms 2020: 1–21 - Shi, Feng; Schirneck, Martin; Friedrich, Tobias; Kötzing, Timo; Neumann, Frank
**Correction to: Reoptimization Time Analysis of Evolutionary Algorithms on Linear Functions Under Dynamic Uniform Constraints**Algorithmica 2020: 3117–3123 - Chauhan, Ankit; Friedrich, Tobias; Rothenberger, Ralf
**Greed is Good for Deterministic Scale-Free Networks**Algorithmica 2020: 3338–3389 - Ghorbani, Ebrahim; Haemers, Willem H.; Reza Maimani, Hamid; Parsaei Majd, Leila
**On sign-symmetric signed graphs**Ars Mathematica Contemporane 2020: 83–93 - Casel, Katrin; Dreier, Jan; Fernau, Henning; Gobbert, Moritz; Kuinke, Philipp; Sanchez Villaamil, Fernando; Schmid, Markus L.; van Leeuwen, Erik Jan
**Complexity of independency and cliquy trees**Discrete Applied Mathematics 2020: 2–15 - Bazgan, Cristina; Brankovic, Ljiljana; Casel, Katrin; Fernau, Henning
**Domination chain: Characterisation, classical complexity, parameterised complexity and approximability**Discrete Applied Mathematics 2020: 23–42 - Akbari, Saieed; Reza Maimani, Hamid; Parsaei Majd, Leila; Wanless, Ian M.
**Zero-sum flows for Steiner systems**Discrete Mathematics 2020: 112074 - Cseh, Ágnes; Heeger, Klaus
**The stable marriage problem with ties and restricted edges**Discrete Optimization 2020: 100571 - Doerr, Benjamin; Krejca, Martin S.
**Significance-based Estimation-of-Distribution Algorithms**IEEE Transactions on Evolutionary Computation 2020: 1025–1034 - Alizadeh, Faezeh; Maimani, Hamid Reza; Parsaei Majd, Leila; Rajabi Parsa, Mina
**Roman 2-domination in graphs and graph products**Iranian Journal of Mathematical Sciences and Informatics Iranian Journal of Mathematical Sciences and Informatics 2020 - Bläsius, Thomas; Friedrich, Tobias; Katzmann, Maximilian; Krohmer, Anton
**Hyperbolic Embeddings for Near-Optimal Greedy Routing**Journal of Experimental Algorithmics (JEA) 2020: 1–18 - Birnick, Johann; Bläsius, Thomas; Friedrich, Tobias; Naumann, Felix; Papenbrock, Thorsten; Schirneck, Martin
**Hitting Set Enumeration with Partial Information for Unique Column Combination Discovery**Proceedings of the VLDB Endowment 2020: 2270–2283 - Battaglia, Francesco; Cucina, Domenico; Rizzo, Manuel
**Parsimonious periodic autoregressive models for time series with evolving trend and seasonality**Statistics and Computing 2020: 77–91 - Friedrich, Tobias; Kötzing, Timo; Lagodzinski, J. A. Gregor; Neumann, Frank; Schirneck, Martin
**Analysis of the (1+1) EA on Subclasses of Linear Functions under Uniform and Linear Constraints**Theoretical Computer Science 2020: 3–19 - Kötzing, Timo; Lagodzinski, J. A. Gregor; Lengler, Johannes; Melnichenko, Anna
**Destructiveness of lexicographic parsimony pressure and alleviation by a concatenation crossover in genetic programming**Theoretical Computer Science 2020: 96–113 - Krejca, Martin S.; Witt, Carsten
**Lower Bounds on the Run Time of the Univariate Marginal Distribution Algorithm on OneMax**Theoretical Computer Science 2020: 143–165 - Doerr, Benjamin; Kötzing, Timo; Lagodzinski, J. A. Gregor; Lengler, Johannes
**The impact of lexicographic parsimony pressure for ORDER/MAJORITY on the run time**Theoretical Computer Science 2020: 144–168 - Bilò, Davide; Lenzner, Pascal
**On the Tree Conjecture for the Network Creation Game**Theory of Computing Systems 2020: 422–443 - Krejca, Martin S.; Witt, Carsten
**Theory of Estimation-of-Distribution Algorithms**Theory of Evolutionary Computation: Recent Developments in Discrete Optimization 2020: 405–442 - Doskoč, Vanja; Kötzing, Timo
**Cautious Limit Learning**Algorithmic Learning Theory (ALT) 2020: 251–276 - Das, Syamantak; Jain, Lavina; Kumar, Nikhil
**A Constant Factor Approximation for Capacitated Min-Max Tree Cover**Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM) 2020: 55:1–55:13 - Bläsius, Thomas; Böther, Maximilian; Fischbeck, Philipp; Friedrich, Tobias; Gries, Alina; Hüffner, Falk; Kißig, Otto; Lenzner, Pascal; Molitor, Louise; Schiller, Leon; Wells, Armin; Wietheger, Simon
**A Strategic Routing Framework and Algorithms for Computing Alternative Paths**Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS) 2020: 10:1–10:14 - Fogel, Sharon; Averbuch-Elor, Hadar; Cohen, Sarel; Mazor, Shai; Litman, Roee
**ScrabbleGAN: Semi-Supervised Varying Length Handwritten Text Generation**Conference on Computer Vision and Pattern Recognition (CVPR) 2020: 4323–4332 - Doskoč, Vanja; Friedrich, Tobias; Göbel, Andreas; Neumann, Aneta; Neumann, Frank; Quinzan, Francesco
**Non-Monotone Submodular Maximization with Multiple Knapsacks in Static and Dynamic Settings**European Conference on Artificial Intelligence (ECAI) 2020: 435–442 - Bläsius, Thomas; Friedrich, Tobias; Schirneck, Martin
**The Minimization of Random Hypergraphs**European Symposium on Algorithms (ESA) 2020: 21:1–21:15 - Garg, Naveen; Kumar, Nikhil
**Dual Half-Integrality for Uncrossable Cut Cover and Its Application to Maximum Half-Integral Flow**European Symposium on Algorithms (ESA) 2020: 55:1–55:13 - Doerr, Benjamin; Krejca, Martin S.
**The Univariate Marginal Distribution Algorithm Copes Well with Deception and Epistasis**Evolutionary Computation in Combinatorial Optimization (EvoCOP) 2020: 51–66Best-Paper Award - Bilò, Davide; Friedrich, Tobias; Lenzner, Pascal; Melnichenko, Anna; Molitor, Louise
**Fair Tree Connection Games with Topology-Dependent Edge Cost**Foundations of Software Technology and Theoretical Computer Science (FSTTCS) 2020: 15:1–15:15 - Doerr, Benjamin; Krejca, Martin S.
**Bivariate Estimation-of-Distribution Algorithms Can Find an Exponential Number of Optima**Genetic and Evolutionary Computation Conference (GECCO) 2020: 796–804 - Bossek, Jakob; Casel, Katrin; Kerschke, Pascal; Neumann, Frank
**The Node Weight Dependent Traveling Salesperson Problem: Approximation Algorithms and Randomized Search Heuristics**Genetic and Evolutionary Computation Conference (GECCO) 2020: 1286–1294 - Friedrich, Tobias; Krejca, Martin S.; Lagodzinski, J. A. Gregor; Rizzo, Manuel; Zahn, Arthur
**Memetic Genetic Algorithms for Time Series Compression by Piecewise Linear Approximation**International Conference on Neural Information Processing (ICONIP) 2020: 592–604 - Echzell, Hagen; Friedrich, Tobias; Lenzner, Pascal; Melnichenko, Anna
**Flow-Based Network Creation Games**International Joint Conference on Artificial Intelligence (IJCAI) 2020: 139–145 - Garg, Naveen; Kumar, Nikhil; Sebö, András
**Integer Plane Multiflow Maximisation: Flow-Cut Gap and One-Quarter-Approximation**Integer Programming and Combinatorial Optimization (IPCO) 2020: 144–157 - Feldmann, Andreas; Issac, Davis; Rai, Ashutosh
**Fixed-Parameter Tractability of the Weighted Edge Clique Partition Problem**International Symposium on Parameterized and Exact Computation (IPEC) 2020: 1–16 - Kumar, Nikhil
**Multicommodity Flows in Planar Graphs with Demands on Faces**International Symposium on Algorithms and Computation (ISAAC) 2020: 1–11 - Bilò, Davide; Bilò, Vittorio; Lenzner, Pascal; Molitor, Louise
**Topological Influence and Locality in Swap Schelling Games**International Symposium on Mathematical Foundations of Computer Science (MFCS) 2020: 15:1–15:15 - Michail, Othon; Skretas, George; Spirakis, G. Paul
**Distributed Computation and Reconfiguration in Actively Dynamic Networks**Principles of Distributed Computing (PODC) 2020: 448–457 - Kötzing, Timo; Witt, Carsten
**Improved Fixed-Budget Results via Drift Analysis**Parallel Problem Solving From Nature (PPSN) 2020: 648–660 - Antoniadis, Antonios; Garg, Naveen; Kumar, Gunjan; Kumar, Nikhil
**Parallel Machine Scheduling to Minimize Energy Consumption**Symposium on Discrete Algorithms (SODA) 2020: 2758–2769 - Feldmann, Michael; Khazraei, Ardalan; Scheideler, Christian
**Time- and Space-Optimal Clock Synchronization in the Beeping Model**Symposium Parallelism in Algorithms and Architectures (SPAA) 2020: 223–233 - Bläsius, Thomas; Fischbeck, Philipp; Friedrich, Tobias; Katzmann, Maximilian
**Solving Vertex Cover in Polynomial Time on Hyperbolic Random Graphs**Symposium on the Theoretical Aspects of Computer Science (STACS) 2020: 25:1–25:14 - Chechik, Shiri; Cohen, Sarel
**Distance sensitivity oracles with subcubic preprocessing time and fast query time**Symposium Theory of Computing (STOC) 2020: 1375–1388 - Becher, Kilian; Lagodzinski, J. A. Gregor; Strufe, Thorsten
**Privacy-Preserving Public Verification of Ethical Cobalt Sourcing**Trust, Security and Privacy in Computing and Communications (TrustCom) 2020: 998–1005 - Held, Stephan; Khazraei, Ardalan
**An Improved Approximation Algorithm for the Uniform Cost-Distance Steiner Tree Problem**Workshop on Approximation and Online Algorithms (WAOA) 2020: 189–203