Prof. Dr. Tobias Friedrich

All Publications in 2020

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

Conference Publications


  • Cautious Limit Learning - Download
    Doskoč, Vanja; Kötzing, TimoCautious Limit Learning. Algorithmic Learning Theory (ALT) 2020: 251-276
  • A Constant Factor Approxi... - Download
    Das, Syamantak; Jain, Lavina; Kumar, NikhilA Constant Factor Approximation for Capacitated Min-Max Tree Cover. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM) 2020: 55:1-55:13
  • A Strategic Routing Frame... - Download
    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; Witheger, SimonA Strategic Routing Framework and Algorithms for Computing Alternative Paths. Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS) 2020: 10:1--10:14
  • ScrabbleGAN: Semi-Supervi... - Download
    Fogel, Sharon; Averbuch-Elor, Hadar; Cohen, Sarel; Mazor, Shai; Litman, RoeeScrabbleGAN: Semi-Supervised Varying Length Handwritten Text Generation. Conference on Computer Vision and Pattern Recognition (CVPR) 2020: 4323-4332
  • Non-Monotone Submodular M... - Download
    Doskoč, Vanja; Friedrich, Tobias; Göbel, Andreas; Neumann, Aneta; Neumann, Frank; Quinzan, FrancescoNon-Monotone Submodular Maximization with Multiple Knapsacks in Static and Dynamic Settings. European Conference on Artificial Intelligence (ECAI) 2020: 435-442
  • The Minimization of Rando... - Download
    Bläsius, Thomas; Friedrich, Tobias; Schirneck, MartinThe Minimization of Random Hypergraphs. European Symposium on Algorithms (ESA) 2020: 21:1-21:15
  • Dual Half-Integrality for... - Download
    Garg, Naveen; Kumar, NikhilDual Half-Integrality for Uncrossable Cut Cover and Its Application to Maximum Half-Integral Flow. European Symposium on Algorithms (ESA) 2020: 55:1-55:13
  • The Univariate Marginal D... - Download
    Doerr, Benjamin; Krejca, Martin S.The Univariate Marginal Distribution Algorithm Copes Well With Deception and Epistasis. Evolutionary Computation in Combinatorial Optimisation (EvoCOP) 2020: 51-66
    Best-Paper Award
  • Fair Tree Connection Game... - Download
    Bilò, Davide; Friedrich, Tobias; Lenzner, Pascal; Melnichenko, Anna; Molitor, LouiseFair Tree Connection Games with Topology-Dependent Edge Cost. Foundations of Software Technology and Theoretical Computer Science (FSTTCS) 2020: 15:1--15:15
  • Bivariate Estimation-of-D... - Download
    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
  • The Node Weight Dependent... - Download
    Bossek, Jakob; Casel, Katrin; Kerschke, Pascal; Neumann, FrankThe Node Weight Dependent Traveling Salesperson Problem: Approximation Algorithms and Randomized Search Heuristics. Genetic and Evolutionary Computation Conference (GECCO) 2020: 1286-1294
  • Memetic Genetic Algorithm... - Download
    Friedrich, Tobias; Krejca, Martin S.; Lagodzinski, J. A. Gregor; Rizzo, Manuel; Zahn, ArthurMemetic Genetic Algorithms for Time Series Compression by Piecewise Linear Approximation. International Conference on Neural Information Processing (ICONIP) 2020: 592-604
  • Flow-Based Network Creati... - Download
    Echzell, Hagen; Friedrich, Tobias; Lenzner, Pascal; Melnichenko, AnnaFlow-Based Network Creation Games. International Joint Conference on Artificial Intelligence (IJCAI) 2020: 139-145
  • Integer Plane Multiflow M... - Download
    Garg, Naveen; Kumar, Nikhil; Sebö, AndrásInteger Plane Multiflow Maximisation: Flow-Cut Gap and One-Quarter-Approximation. Integer Programming and Combinatorial Optimization (IPCO) 2020: 144-157
  • Feldmann, Andreas; Issac, Davis; Rai, AshutoshFixed-Parameter Tractability of the Weighted Edge Clique Partition Problem. International Symposium on Parameterized and Exact Computation (IPEC) 2020
  • Multicommodity Flows in P... - Download
    Kumar, NikhilMulticommodity Flows in Planar Graphs with Demands on Faces. International Symposium on Algorithms and Computation (ISAAC) 2020
  • Topological Influence and... - Download
    Bilò, Davide; Bilò, Vittorio; Lenzner, Pascal; Molitor, LouiseTopological Influence and Locality in Swap Schelling Games. International Symposium on Mathematical Foundations of Computer Science (MFCS) 2020: 15:1--15:15
  • Improved Fixed-Budget Res... - Download
    Kötzing, Timo; Witt, CarstenImproved Fixed-Budget Results via Drift Analysis. Parallel Problem Solving From Nature (PPSN) 2020: 648-660
  • Parallel Machine Scheduli... - Download
    Antoniadis, Antonios; Garg, Naveen; Kumar‎, Gunjan; Kumar, NikhilParallel Machine Scheduling to Minimize Energy Consumption. Symposium on Discrete Algorithms (SODA) 2020: 2758-2769
  • Feldmann, Michael; Khazraei, Ardalan; Scheideler, ChristianTime- and Space-Optimal Clock Synchronization in the Beeping Model. Symposium Parallelism in Algorithms and Architectures (SPAA) 2020
  • Solving Vertex Cover in P... - Download
    Bläsius, Thomas; Fischbeck, Philipp; Friedrich, Tobias; Katzmann, MaximilianSolving Vertex Cover in Polynomial Time on Hyperbolic Random Graphs. Symposium on the Theoretical Aspects of Computer Science (STACS) 2020: 25:1-25:14
  • Distance sensitivity orac... - Download
    Chechik, Shiri; Cohen, SarelDistance sensitivity oracles with subcubic preprocessing time and fast query time. Symposium Theory of Computing (STOC) 2020: 1375-1388
  • Privacy-Preserving Public... - Download
    Becher, Kilian; Lagodzinski, J. A. Gregor; Strufe, ThorstenPrivacy-Preserving Public Verification of Ethical Cobalt Sourcing. Trust, Security and Privacy in Computing and Communications (TrustCom) 2020
  • Held, Stephan; Khazraei, ArdalanAn Improved Approximation Algorithm for the Uniform Cost-Distance Steiner Tree Problem. Workshop on Approximation and Online Algorithms (WAOA) 2020

Journal Publications


  • The Complexity of Cake Cu... - Download
    Cseh, Ágnes; Fleiner, TamásThe Complexity of Cake Cutting with Unequal Shares. ACM Transactions on Algorithms 2020: 1-21
  • Correction to: Reoptimiza... - Download
    Shi, Feng; Schirneck, Martin; Friedrich, Tobias; Kötzing, Timo; Neumann, FrankCorrection to: Reoptimization Time Analysis of Evolutionary Algorithms on Linear Functions Under Dynamic Uniform Constraints. Algorithmica 2020: 3117-3123
  • Greed is Good for Determi... - Download
    Chauhan, Ankit; Friedrich, Tobias; Rothenberger, RalfGreed is Good for Deterministic Scale-Free Networks. Algorithmica 2020: 3338–3389
  • Complexity of independenc... - Download
    Casel, Katrin; Dreier, Jan; Fernau, Henning; Gobbert, Moritz; Kuinke, Philipp; Sanchez Villaamil, Fernando; Schmid, Markus L.; van Leeuwen, Erik JanComplexity of independency and cliquy trees. Discrete Applied Mathematics 2020: 2-15
  • Domination chain: Charact... - Download
    Bazgan, Cristina; Brankovic, Ljiljana; Casel, Katrin; Fernau, HenningDomination chain: Characterisation, classical complexity, parameterised complexity and approximability. Discrete Applied Mathematics 2020: 23-42
  • The stable marriage probl... - Download
    Cseh, Ágnes; Heeger, KlausThe stable marriage problem with ties and restricted edges. Discrete Optimization 2020: 100571
  • Hyperbolic Embeddings for... - Download
    Bläsius, Thomas; Friedrich, Tobias; Katzmann, Maximilian; Krohmer, AntonHyperbolic Embeddings for Near-Optimal Greedy Routing. Journal of Experimental Algorithmics (JEA) 2020
  • Hitting Set Enumeration w... - Download
    Birnick, Johann; Bläsius, Thomas; Friedrich, Tobias; Naumann, Felix; Papenbrock, Thorsten; Schirneck, MartinHitting Set Enumeration with Partial Information for Unique Column Combination Discovery. Proceedings of the VLDB Endowment 2020: 2270 - 2283
  • Parsimonious periodic aut... - Download
    Battaglia, Francesco; Cucina, Domenico; Rizzo, ManuelParsimonious periodic autoregressive models for time series with evolving trend and seasonality. Statistics and Computing 2020: 77-91
  • Analysis of the (1+1) EA ... - Download
    Friedrich, Tobias; Kötzing, Timo; Lagodzinski, J. A. Gregor; Neumann, Frank; Schirneck, MartinAnalysis of the (1+1) EA on Subclasses of Linear Functions under Uniform and Linear Constraints. Theoretical Computer Science 2020: 3-19
  • Destructiveness of lexico... - Download
    Kötzing, Timo; Lagodzinski, J. A. Gregor; Lengler, Johannes; Melnichenko, AnnaDestructiveness of lexicographic parsimony pressure and alleviation by a concatenation crossover in genetic programming. Theoretical Computer Science 2020: 96--113
  • Lower Bounds on the Run T... - Download
    Krejca, Martin S.; Witt, CarstenLower Bounds on the Run Time of the Univariate Marginal Distribution Algorithm on OneMax. Theoretical Computer Science 2020: 143-165
  • The impact of lexicograph... - Download
    Doerr, Benjamin; Kötzing, Timo; Lagodzinski, J. A. Gregor; Lengler, JohannesThe impact of lexicographic parsimony pressure for ORDER/MAJORITY on the run time. Theoretical Computer Science 2020: 144--168
  • Casel, Katrin; Fernau, Henning; Gaspers, Serge; Gras, Benjamin; Schmid, Markus L.On the Complexity of the Smallest Grammar Problem over Fixed Alphabets. Theory of Computing Systems 2020
  • On the Tree Conjecture fo... - Download
    Bilò, Davide; Lenzner, PascalOn the Tree Conjecture for the Network Creation Game. Theory of Computing Systems 2020: 422--443
  • Significance-based Estima... - Download
    Doerr, Benjamin; Krejca, Martin S.Significance-based Estimation-of-Distribution Algorithms. Transactions on Evolutionary Computation 2020: 1025-1034
  • Learning Half-Spaces and ... - Download
    Khazraei, Ardalan; Kötzing, Timo; Seidel, KarenLearning Half-Spaces and other Concept Classes in the Limit with Iterative Learners. CoRR 2020
    ArXiv preprint
  • Efficiently Enumerating H... - Download
    Bläsius, Thomas; Friedrich, Tobias; Lischeid, Julius; Meeks, Kitty; Schirneck, MartinEfficiently Enumerating Hitting Sets of Hypergraphs Arising in Data Profiling. CoRR 2020
    ArXiv preprint
  • Learning Languages in the... - Download
    Kötzing, Timo; Seidel, KarenLearning Languages in the Limit from Positive Information with Finitely Many Memory Changes. CoRR 2020
    ArXiv preprint