# All Publications

The following listing contains all publications of the current members of the Algorithm Engineering group. Loading the page might take a few seconds depending on your connection. Alternatively, see the shorter list of current publications.

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

- years: 2020, 2019, 2018, 2017, 2016, 2015, 2014, 2013, 2012, 2011, 2010
- researchers: Prof. Dr. Tobias Friedrich, Dr. Thomas Bläsius, Dr. Katrin Casel, Dr. Ágnes Cseh, Dr. Andreas Göbel, Dr. Davis Issac, Dr. Timo Kötzing, Dr. Martin Krejca, Dr. Pascal Lenzner
- PhD students: Vanja Doskoč, Ziena Elijazyfer, Philipp Fischbeck, Maximilian Katzmann, Ardalan Khazraei, Gregor Lagodzinski, Anna Melnichenko, Louise Molitor, Stefan Neubert, Francesco Quinzan, Ralf Rothenberger, Martin Schirneck, Karen Seidel, Christopher Weyand
- 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

2020

- Greed is Good for Deterministic Scale-Free Networks. Algorithmica 2020
- Erratum to: Reoptimization Time Analysis of Evolutionary Algorithms on Linear Functions Under Dynamic Uniform Constraints. Algorithmica 2020
- Complexity of independency and cliquy trees. Discrete Applied Mathematics 2020: 2-15
- Domination chain: Characterisation, classical complexity, parameterised complexity and approximability. Discrete Applied Mathematics 2020: 23-42
- Hyperbolic Embeddings for Near-Optimal Greedy Routing. Journal of Experimental Algorithmics (JEA) 2020
- Parsimonious periodic autoregressive models for time series with evolving trend and seasonality. Statistics and Computing 2020: 77-91
- Analysis of the (1+1) EA on Subclasses of Linear Functions under Uniform and Linear Constraints. Theoretical Computer Science 2020: 3-19
- Destructiveness of lexicographic parsimony pressure and alleviation by a concatenation crossover in genetic programming. Theoretical Computer Science 2020: 96--113
- Lower Bounds on the Run Time of the Univariate Marginal Distribution Algorithm on OneMax. Theoretical Computer Science 2020: 143-165
- The impact of lexicographic parsimony pressure for ORDER/MAJORITY on the run time. Theoretical Computer Science 2020: 144--168
- On the Tree Conjecture for the Network Creation Game. Theory of Computing Systems 2020: 422--443
- Significance-based Estimation-of-Distribution Algorithms. Transactions on Evolutionary Computation 2020
- Theory of Estimation-of-Distribution Algorithms. Theory of Evolutionary Computation: Recent Developments in Discrete Optimization 2020: 405-442
- Cautious Limit Learning. Algorithmic Learning Theory (ALT) 2020
- Non-Monotone Submodular Maximization with Multiple Knapsacks in Static and Dynamic Settings. European Conference on Artificial Intelligence (ECAI) 2020
- The Univariate Marginal Distribution Algorithm Copes Well With Deception and Epistasis. Evolutionary Computation in Combinatorial Optimisation (EvoCOP) 2020: 51-66Best-Paper Award
- The Node Weight Dependent Traveling Salesperson Problem: Approximation Algorithms and Randomized Search Heuristics. Genetic and Evolutionary Computation Conference (GECCO) 2020
- Bivariate Estimation-of-Distribution Algorithms Can Find an Exponential Number of Optima. Genetic and Evolutionary Computation Conference (GECCO) 2020
- Flow-Based Network Creation Games. International Joint Conference on Artificial Intelligence (IJCAI) 2020
- Time- and Space-Optimal Clock Synchronization in the Beeping Model. Symposium Parallelism in Algorithms and Architectures (SPAA) 2020
- Solving Vertex Cover in Polynomial Time on Hyperbolic Random Graphs. Symposium on the Theoretical Aspects of Computer Science (STACS) 2020: 25:1-25:14

2019

- Hadwiger's conjecture for squares of 2-trees. European Journal of Combinatorics 2019
- Routing for On-Street Parking Search using Probabilistic Data. AI Communications 2019: 113-124
- New and Simple Algorithms for Stable Flow Problems. Algorithmica 2019
- Solving Problems with Unknown Solution Length at Almost No Extra Cost. Algorithmica 2019: 703-748
- Reoptimization Time Analysis of Evolutionary Algorithms on Linear Functions Under Dynamic Uniform Constraints. Algorithmica 2019: 828-857
- Island Models Meet Rumor Spreading. Algorithmica 2019: 886-915
- Quasi-random Image Transition and Animation. Australian Journal of Intelligent Information Processing Systems 2019: 10-18
- Selected open problems in Matching Under Preferences. Bulletin of the European Association for Theoretical Computer Science 2019
- Detection and estimation of additive outliers in seasonal time series. Computational Statistics 2019: 1-17
- Surfing on the seascape: Adaptation in a changing environment. Evolution: International Journal of Organic Evolution 2019: 1356-1374
- How to Draw a Planarization. Graph Algorithms and Applications 2019: 653-682
- Paths to stable allocations. International Journal of Game Theory 2019
- Multiple changepoint detection for periodic autoregressive models with an application to river flow analysis. Stochastic Environmental Research and Risk Assessment 2019: 1137-1157
- Unbiasedness of Estimation-of-Distribution Algorithms. Theoretical Computer Science 2019: 46-59
- First-hitting times under drift. Theoretical Computer Science 2019: 51-69
- The Stable Roommates Problem with Short Lists. Theory of Computing Systems 2019
- Greedy Maximization of Functions with Bounded Curvature Under Partition Matroid Constraints. Conference on Artificial Intelligence (AAAI) 2019: 2272-2279
- Pareto Optimization for Subset Selection with Dynamic Cost Constraints. Conference on Artificial Intelligence (AAAI) 2019: 2354-2361
- From Hotelling to Load Balancing: Approximation and the Principle of Minimum Differentiation. Autonomous Agents and Multiagent Systems (AAMAS) 2019: 1949-1951
- Efficiently Enumerating Hitting Sets of Hypergraphs Arising in Data Profiling. Algorithm Engineering and Experiments (ALENEX) 2019: 130-143
- Limit Learning Equivalence Structures. Algorithmic Learning Theory (ALT) 2019: 383-403
- Extension of vertex cover and independent set in some classes of graphs and generalizations. International Conference on Algorithms and Complexity (CIAC) 2019: 124-136
- Efficiently Generating Geometric Inhomogeneous and Hyperbolic Random Graphs. European Symposium on Algorithms (ESA) 2019: 21:2-21:14EATCS Best Paper Award
- Extension of some edge graph problems: standard and parameterized complexity. Fundamentals of Computation Theory (FCT) 2019: 185-200
- Multiplicative Up-Drift. Genetic and Evolutionary Computation Conference (GECCO) 2019
- The Satisfiability Threshold for Non-Uniform Random 2-SAT. International Colloquium on Automata, Languages and Programming (ICALP) 2019: 61:1-61:14
- 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
- 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
- Sharpness of the Satisfiability Threshold for Non-Uniform Random \(k\)-SAT.International Joint Conference on Artificial Intelligence (IJCAI) 2019: 6151-6155
- Random Subgroups of Rationals. Mathematical Foundations of Computer Science (MFCS) 2019: 25:1-25:14
- Geometric Network Creation Games. Symposium on Parallelism in Algorithms and Architectures (SPAA) 2019: 323-332
- Pairwise Preferences in the Stable Marriage Problem. Symposium Theoretical Aspects of Computer Science (STACS) 2019
- From Graph Theory to Network Science: The Natural Emergence of Hyperbolicity. Symposium Theoretical Aspects of Computer Science (STACS) 2019: 5:1–5:9
- 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
- Understanding the Effectiveness of Data Reduction in Public Transportation Networks. Workshop on Algorithms and Models for the Web Graph (WAW) 2019: 87-101
- Convergence and Hardness of Strategic Schelling Segregation. Web and Internet Economics (WINE) 2019: 156-170
- Theoretical Analyses of Univariate Estimation-of-Distribution Algorithms. PhD thesis, Hasso Plattner Institute, University of Potsdam 2019
- FOGA ’19: Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms. 2019ACM.Editorship
- Theory of Randomized Optimization Heuristics. Dagstuhl Reports 2019: 61-94

2018

- Sampling in space restricted settings. Algorithmica 2018: 1439-1458
- Matchings with Lower Quotas: Algorithms and Complexity. Algorithmica 2018
- Simultaneous Embedding: Edge Orderings, Relative Positions, Cutvertices. Algorithmica 2018: 1214-1277
- Preface to the Special Issue on Theory of Genetic and Evolutionary Computation. Algorithmica 2018: 1575-1578
- Static and Self-Adjusting Mutation Strengths for Multi-valued Decision Variables. Algorithmica 2018: 1732-1768
- Cliques in Hyperbolic Random Graphs. Algorithmica 2018: 2324-2344
- Clustering with Lower-Bounded Sizes - A General Graph-Theoretic Framework. Algorithmica 2018: 2517-2550
- De-anonymization of Heterogeneous Random Graphs in Quasilinear Time. Algorithmica 2018: 3397–3427
- Learning from Informants: Relations between Learning Success Criteria. ArXiv 2018: 37
- Local and Union Boxicity. Discrete Mathematics 2018: 1307 - 1315
- Scalable Exact Visualization of Isocontours in Road Networks via Minimum-Link Paths. Journal of Computational Geometry 2018: 27-73
- Statistical and Computational Tradeoff in Genetic Algorithm-Based Estimation. Journal of Statistical Computation and Simulation 2018: 3081-3097
- Popular edges and dominant matchings. Mathematical Programming 2018
- On the diameter of hyperbolic random graphs. SIAM Journal on Discrete Mathematics 2018: 1314-1334
- Unbounded Discrepancy of Deterministic Random Walks on Grids. SIAM Journal on Discrete Mathematics 2018: 2441-2452
- The many facets of upper domination. Theoretical Computer Science 2018: 2-25
- Escaping Local Optima Using Crossover with Emergent Diversity. Transactions on Evolutionary Computation 2018: 484-497
- Efficient Embedding of Scale-Free Graphs in the Hyperbolic Plane. Transactions on Networking 2018: 920-933
- Confident Iterative Learning in Computational Learning Theory. Current Trends in Theory and Practice of Computer Science (SOFSEM) 2018: 30-42
- Periodic Autoregressive Models with Multiple Structural Changes by Genetic Algorithms. Mathematical and Statistical Methods for Actuarial Sciences and Finance (MAF) 2018: 107-110
- Hyperbolic Embeddings for Near-Optimal Greedy Routing. Algorithm Engineering and Experiments (ALENEX) 2018: 199-208
- Popular Matchings in Complete Graphs. Foundations of Software Technology and Theoretical Computer Science (FSTTCS) 2018
- Escaping Large Deceptive Basins of Attraction with Heavy Mutation Operators. Genetic and Evolutionary Computation Conference (GECCO) 2018: 293-300
- Improving the Run Time of the (1+1) Evolutionary Algorithm with Luby Sequences. Genetic and Evolutionary Computation Conference (GECCO) 2018: 301-308
- Randomized Greedy Algorithms for Covering Problems. Genetic and Evolutionary Computation Conference (GECCO) 2018: 309-315
- Significance-based Estimation-of-Distribution Algorithms. Genetic and Evolutionary Computation Conference (GECCO) 2018: 1483-1490
- Spanning tree congestion and computation of gyori lovasz partition. International Colloquium on Automata, Languages, and Programming (ICALP) 2018
- Efficient Shortest Paths in Scale-Free Networks with Underlying Hyperbolic Geometry. International Colloquium on Automata, Languages, and Programming (ICALP) 2018: 20:1-20:14
- Resolving Conflicts for Lower-Bounded Clustering. International Symposium on Parameterized and Exact Computation (IPEC) 2018: 23:1-23:14
- Identification of Multiregime Periodic Autoregressive Models by Genetic Algorithms. International Conference on Time Series and Forecasting (ITISE) 2018: 396-407
- EvoCells – A Treemap Layout Algorithm for Evolving Tree Data. 9th International Conference on Information Visualization Theory and Applications (IVAPP) 2018: 273-280
- Algorithms and bounds for very strong rainbow coloring. Latin American Symposium on Theoretical Informatics Conference (LATIN) 2018
- Rainbow Vertex Coloring Bipartite Graphs and Chordal Graphs. Mathematical Foundations of Computer Science (MFCS) 2018
- Counting Homomorphisms to Trees Modulo a Prime. Mathematical Foundations of Computer Science (MFCS) 2018: 49:1-49:13
- Destructiveness of Lexicographic Parsimony Pressure and Alleviation by a Concatenation Crossover in Genetic Programming. Parallel Problem Solving From Nature (PPSN) 2018: 42-54
- First-Hitting Times for Finite State Spaces. Parallel Problem Solving From Nature (PPSN) 2018: 79-91
- First-Hitting Times Under Additive Drift. Parallel Problem Solving From Nature (PPSN) 2018: 92-104
- Ring Migration Topology Helps Bypassing Local Optima. Parallel Problem Solving From Nature (PPSN) 2018: 129-140
- Heavy-tailed Mutation Operators in Single-Objective Combinatorial Optimization. Parallel Problem Solving From Nature (PPSN) 2018: 134-145
- Schelling Segregation with Strategic Agents. Symposium on Algorithmic Game Theory (SAGT) 2018
- The Complexity of Cake Cutting with Unequal Shares. Symposium Algorithmic Game Theory (SAGT) 2018
- Sharpness of the Satisfiability Threshold for Non-Uniform Random k-SAT. Theory and Applications of Satisfiability Testing (SAT) 2018: 273-291Best Paper Award
- Generalized Periodic Autoregressive Models for Trend and Seasonality Varying Time Series. Scientific Meeting of the Italian Statistical Society (SIS) 2018
- Memory-restricted Routing With Tiled Map Data. Systems, Man, and Cybernetics (SMC) 2018: 3347-3354
- On the Tree Conjecture for the Network Creation Game. Symposium on the Theoretical Aspects of Computer Science (STACS) 2018: 14:1-14:15
- Towards a Systematic Evaluation of Generative Network Models. Workshop on Algorithms and Models for the Web Graph (WAW) 2018: 99-114
- On the Effectiveness of Data Reduction for Covering Problems in Real-World Transit Networks. Master Thesis, Hasso Plattner Institute 2018
- Mechanisms for Network Creation. Master Thesis, Hasso Plattner Institute 2018
- Contributions on Evolutionary Computation for Statistical Inference. Doctoral Dissertation, Sapienza University of Rome 2018

2017

- Minimizing Maximum (Weighted) Flow-Time on Related and Unrelated Machines. Algorithmica 2017: 515-536
- Time Complexity Analysis of Evolutionary Algorithms on Random Satisfiable k-CNF Formulas. Algorithmica 2017: 561-586
- On the connection between interval size functions and path counting. Computational Complexity 2017: 421-467
- On Variability Analysis of Evolutionary Algorithm-Based Estimation. Conference of the Classification and Data Analysis Group (CLADAG) 2017: 237-242
- Amplifiers for the Moran Process. Journal of the ACM 2017: 5:1-5:90
- Popular Matchings with Two-Sided Preferences and One-Sided Ties. SIAM Journal on Discrete Mathematics 2017
- The Compact Genetic Algorithm is Efficient under Extreme Gaussian Noise. Transactions on Evolutionary Computation 2017: 477-490
- Fit fürs Studium - Informatik. 2017Rheinwerk Computing.
- Zu mathematischen Argumentationen eines Experten aus einer semiotischen Perspektive. Beiträge zum Mathematikunterricht 2017 2017: 897-900
- A Generic Bet-and-Run Strategy for Speeding Up Stochastic Local Search. Conference on Artificial Intelligence (AAAI) 2017: 801-807
- Systematic Exploration of Larger Local Search Neighborhoods for the Minimum Vertex Cover Problem. Conference on Artificial Intelligence (AAAI) 2017: 846-852
- Phase Transitions for Scale-Free SAT Formulas. Conference on Artificial Intelligence (AAAI) 2017: 3893-3899
- What's Hot in Evolutionary Computation. Conference on Artificial Intelligence (AAAI) 2017: 5064-5066
- Automatic Learning from Repetitive Texts. Algorithmic Learning Theory (ALT) 2017: 129-150
- Normal Forms in Semantic Language Identification. Algorithmic Learning Theory (ALT) 2017: 493-516
- Scaling up Local Search for Minimum Vertex Cover in Large Graphs by Parallel Kernelization. Australasian Conference on Artificial Intelligence (AUSAI) 2017: 131-143
- Improving local search in a minimum vertex cover solver for classes of networks. Congress on Evolutionary Computation (CEC) 2017: 1704-1711
- TrussFab: Fabricating Sturdy Large-Scale Structures on Desktop 3D Printers. Human Factors in Computing Systems (CHI) 2017: 2606-2616
- Bounds on the Satisfiability Threshold for Power Law Distributed Random SAT. European Symposium on Algorithms (ESA) 2017: 37:1-37:15
- Resampling vs Recombination: a Statistical Run Time Estimation. Foundations of Genetic Algorithms (FOGA) 2017: 25-35