Hasso-Plattner-Institut
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

2020

  • Cautious Limit Learning - Download
    Doskoč, Vanja; Kötzing, Timo Cautious Limit Learning. Algorithmic Learning Theory (ALT) 2020: 251–276
     
  • A Constant Factor Approxi... - Download
    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
     
  • 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, 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
     
  • ScrabbleGAN: Semi-Supervi... - Download
    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
     
  • Non-Monotone Submodular M... - Download
    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
     
  • The Minimization of Rando... - Download
    Bläsius, Thomas; Friedrich, Tobias; Schirneck, Martin The Minimization of Random Hypergraphs. European Symposium on Algorithms (ESA) 2020: 21:1–21:15
     
  • Dual Half-Integrality for... - Download
    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
     
  • 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, Louise Fair 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, Frank The 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, Arthur Memetic 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, Anna Flow-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á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
     
  • Multicommodity Flows in P... - Download
    Kumar, Nikhil Multicommodity Flows in Planar Graphs with Demands on Faces. International Symposium on Algorithms and Computation (ISAAC) 2020: 1–11
     
  • Topological Influence and... - Download
    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
     
  • Improved Fixed-Budget Res... - Download
    Kötzing, Timo; Witt, Carsten Improved 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, 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
     
  • Solving Vertex Cover in P... - Download
    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
     
  • Distance sensitivity orac... - Download
    Chechik, Shiri; Cohen, Sarel Distance 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, 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
     

Journal Publications

2020

  • The Complexity of Cake Cu... - Download
    Cseh, Ágnes; Fleiner, Tamás The 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, Frank Correction 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, Ralf Greed 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 Jan Complexity of independency and cliquy trees. Discrete Applied Mathematics 2020: 2–15
     
  • Domination chain: Charact... - Download
    Bazgan, Cristina; Brankovic, Ljiljana; Casel, Katrin; Fernau, Henning Domination chain: Characterisation, classical complexity, parameterised complexity and approximability. Discrete Applied Mathematics 2020: 23–42
     
  • The stable marriage probl... - Download
    Cseh, Ágnes; Heeger, Klaus The stable marriage problem with ties and restricted edges. Discrete Optimization 2020: 100571
     
  • Hyperbolic Embeddings for... - Download
    Bläsius, Thomas; Friedrich, Tobias; Katzmann, Maximilian; Krohmer, Anton Hyperbolic 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, Martin Hitting 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, Manuel Parsimonious 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, Martin Analysis 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, Anna 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 T... - Download
    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
     
  • The impact of lexicograph... - Download
    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
     
  • On the Tree Conjecture fo... - Download
    Bilò, Davide; Lenzner, Pascal On 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
     
  • Theory of Estimation-of-D... - Download
    Krejca, Martin; Witt, Carsten Theory of Estimation-of-Distribution Algorithms. Theory of Evolutionary Computation: Recent Developments in Discrete Optimization 2020: 405–442
     
  • Cautious Limit Learning - Download
    Doskoč, Vanja; Kötzing, Timo Cautious Limit Learning. Algorithmic Learning Theory (ALT) 2020: 251–276
     
  • A Constant Factor Approxi... - Download
    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
     
  • 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, 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
     
  • ScrabbleGAN: Semi-Supervi... - Download
    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
     
  • Non-Monotone Submodular M... - Download
    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
     
  • The Minimization of Rando... - Download
    Bläsius, Thomas; Friedrich, Tobias; Schirneck, Martin The Minimization of Random Hypergraphs. European Symposium on Algorithms (ESA) 2020: 21:1–21:15
     
  • Dual Half-Integrality for... - Download
    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
     
  • 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, Louise Fair 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, Frank The 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, Arthur Memetic 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, Anna Flow-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á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
     
  • Multicommodity Flows in P... - Download
    Kumar, Nikhil Multicommodity Flows in Planar Graphs with Demands on Faces. International Symposium on Algorithms and Computation (ISAAC) 2020: 1–11
     
  • Topological Influence and... - Download
    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
     
  • Improved Fixed-Budget Res... - Download
    Kötzing, Timo; Witt, Carsten Improved 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, 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
     
  • Solving Vertex Cover in P... - Download
    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
     
  • Distance sensitivity orac... - Download
    Chechik, Shiri; Cohen, Sarel Distance 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, 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
     
  • New Conditions via Markov... - Download
    Pappik, Marcus New Conditions via Markov Chains: Approximating Partition Functions of Abstract Polymer Models without Cluster Expansion. master’s thesis, Hasso Plattner Institute 2020