Helsinki · Finland

20–24 August 2018


ESA 2018: Program

26th Annual European Symposium on Algorithms

Keynote speakers

Claire Mathieu

Claire Mathieu · CNRS, Paris

Claire Mathieu does research on the design and analysis of algorithms, with a focus on approximation algorithms, particularly approximation schemes for NP-hard problems. A former student of Ecole normale supérieure, she received a PhD in Computer Science in 1988 at Paris-Sud University. She has held research and faculty positions at CNRS, Paris-Sud University, Ecole Polytechnique, Brown University, and Collège de France. She is currently a CNRS research director in Paris, France.

Tim Roughgarden

Tim Roughgarden · Stanford

Tim Roughgarden is a Professor of Computer Science and (by courtesy) Management Science and Engineering at Stanford University. He joined the Stanford faculty in 2004, following a PhD at Cornell and a postdoc at UC Berkeley. His research interests include the many connections between computer science and economics, as well as the design, analysis, applications, and limitations of algorithms. For his research, he has been awarded the ACM Grace Murray Hopper Award, the Presidential Early Career Award for Scientists and Engineers (PECASE), the Kalai Prize in Computer Science and Game Theory, the Social Choice and Welfare Prize, the Mathematical Programming Society’s Tucker Prize, and the EATCS-SIGACT Gödel Prize. He was an invited speaker at the 2006 International Congress of Mathematicians, the Shapley Lecturer at the 2008 World Congress of the Game Theory Society, and a Guggenheim Fellow in 2017. His books include Twenty Lectures on Algorithmic Game Theory (2016) and Algorithms Illuminated (2017).

Accepted papers

Corrie Jacobien Carstens, Michael Hamann, Ulrich Meyer, Manuel Penschuck, Hung Tran and Dorothea Wagner. Parallel and I/O-efficient Randomisation of Massive Networks using Global Curveball Trades
Michał Pilipczuk, Erik Jan van Leeuwen and Andreas Wiese. Quasi-polynomial time approximation schemes for packing and covering problems in planar graphs
Rajiv Raman and Saurabh Ray. Planar Support for Non-Piercing Regions and Applications
Shilpa Garg and Tobias Mömke. A QPTAS for Gapless MEC
Arijit Ghosh, Sudeshna Kolay and Gopinath Mishra. FPT algorithms for embedding into low complexity graphic metrics
Yixin Cao, Ashutosh Rai, R.B. Sandeep and Junjie Ye. A Polynomial Kernel for Diamond-Free Editing
Euiwoong Lee and Sahil Singla. Optimal Online Contention Resolution Schemes via Ex-Ante Prophet Inequalities
Roberto Grossi and Luca Versari. Round-Hashing for Data Storage: Distributed Servers and External-Memory Tables
Anupam Prakash, Miklos Santha and Gabor Ivanyos. On learning linear functions from subset and its applications in quantum computing
Sunil Arya, Guilherme D. Da Fonseca and David Mount. Approximate Convex Intersection Detection with Applications to Width and Minkowski Sums
Alexander van der Grinten, Elisabetta Bergamini, Oded Green, David Bader and Henning Meyerhenke. Scalable Katz Ranking Computation in Large Dynamic Graphs
Yan Gu, Yihan Sun and Guy Blelloch. Algorithmic Building Blocks for Asymmetric Memories
Gramoz Goranci, Monika Henzinger and Pan Peng. Dynamic Effective Resistances and Approximate Schur Complement on Separable Graphs
Nicolas Auger, Vincent Jugé, Cyril Nicaud and Carine Pivoteau. On the Worst-Case Complexity of TimSort
J. Ian Munro and Sebastian Wild. Nearly-Optimal Natural Mergesort: Practically Fast Sorting Methods That Optimally Adapt to Existing Runs
Stefan Kratsch and Florian Nelles. Efficient and adaptive parameterized algorithms on modular decompositions
Marvin Künnemann. On Nondeterministic Derandomization of Freivalds’ Algorithm: Consequences, Avenues and Algorithmic Progress
Sankardeep Chakraborty, Anish Mukherjee, Venkatesh Raman and Srinivasa Rao Satti. A Framework for In-place Graph Algorithms
Rajesh Chitnis, Andreas Emil Feldmann and Pasin Manurangsi. Parameterized Approximation Algorithms for Bidirected Steiner Network Problems
Hsien-Chih Chang, Pawel Gawrychowski, Shay Mozes and Oren Weimann. Near-Optimal Distance Preserver for Planar Graphs
Hicham El-Zein, Meng He, Ian Munro and Bryce Sandlund. Improved Time and Space Bounds for Dynamic Range Mode and Least Frequent Element
Fedor Fomin, Fahad Panolan, Ramanujan M. S. and Saket Saurabh. On the Optimality of Pseudo-polynomial Algorithms for Integer Programming
Bart M. P. Jansen and Astrid Pieterse. Polynomial Kernels for Hitting Forbidden Minors under Structural Parameterizations
Dani Dorfman, Haim Kaplan, Laszlo Kozma, Seth Pettie and Uri Zwick. Improved bounds for multipass pairing heaps and path-balanced binary search trees
Shay Solomon and Nicole Wein. Improved Dynamic Graph Coloring
Diptarka Chakraborty, Debarati Das, Michal Koucky and Nitin Saurabh. Space-Optimal Quasi-Gray Codes with Logarithmic Read Complexity
Dominik Kempa, Alberto Policriti, Nicola Prezza and Eva Rotenberg. String Attractors: Verification and Optimization
Gramoz Goranci, Monika Henzinger and Dariusz Leniowski. A Tree Structure For Dynamic Facility Location
Barnaby Martin, Daniel Paulusma and Erik Jan van Leeuwen. Disconnected Cuts in Claw-free Graphs
Maximilian Probst. On the complexity of the (approximate) nearest colored node problem
Matthias Englert, David Mezlaf and Matthias Westermann. Online Makespan Scheduling with Job Migration on Uniform Machines
Michael Matheny and Jeff Phillips. Practical Low-Dimensional Halfspace Range Space Sampling
Mordecai Golin, John Iacono, Stefan Langerman, Ian Munro and Yakov Nekrich. Dynamic Trees with Almost-Optimal Access Cost
Vít Jelínek, Michal Opler and Pavel Valtr. Generalized Coloring of Permutations
Amos Korman, Yoav Rodeh and Lucas Boczkowski. Searching a Tree with Permanently Noisy Advice
Sebastian Brandt, Seth Pettie and Jara Uitto. Fine-grained Lower Bounds on Cops and Robbers
Daniel R. Schmidt, Bernd Zey and François Margot. An exact algorithm for the Steiner forest problem
Fedor Fomin, Petr Golovach and Jean-Florent Raymond. On the tractability of optimization problems on H-graphs
Hu Ding and Manni Liu. On Geometric Prototype And Applications
Johannes K. Fichte, Markus Hecher, Stefan Woltran and Markus Zisser. Weighted Model Counting on the GPU by Exploiting Small Treewidth
Bart M. P. Jansen and Jesper Nederlof. Computing the Chromatic Number Using Graph Decompositions via Matrix Rank
Iyad Kanj, Christian Komusiewicz, Manuel Sorge and Erik Jan van Leeuwen. Solving Partition Problems Almost Always Requires Pushing Many Vertices Around
Jacob Holm, Giuseppe F. Italiano, Adam Karczmarz, Jakub Łącki and Eva Rotenberg. Decremental SPQR-trees for Planar Graphs
Cameron Chalk, Austin Luchsinger, Robert Schweller and Tim Wylie. Self-Assembly of Any Shape with Constant Tile Types using High Temperature
Siddharth Pritam, Jean-Daniel Boissonnat and Divyansh Pareek. Strong Collapse for Persistence
Luca Becchetti, Andrea Clementi, Pasin Manurangsi, Emanuele Natale, Francesco Pasquale, Prasad Raghavendra and Luca Trevisan. Average whenever you meet: Opportunistic protocols for community detection
János Balogh, József Békési, György Dósa, Leah Epstein and Asaf Levin. A new and improved algorithm for online bin packing
Amariah Becker, Philip Klein and David Saulpic. Polynomial-time approximation schemes for k-center, k-median, and capacitated vehicle routing in bounded highway dimension
Gal Shahaf, Michael Dinitz and Michael Schapira. Large Low-Diameter Graphs are Good Expanders
Sara Ahmadian, Umang Bhaskar, Laura Sanita and Chaitanya Swamy. Algorithms for Inverse Optimization Problems
Max Bannach and Sebastian Berndt. Practical Access to Dynamic Programming on Tree Decompositions
Nabil Mustafa and Saurabh Ray. On a Problem of Danzer
Marek Cygan, Artur Czumaj, Marcin Mucha and Piotr Sankowski. Online Facility Location with Deletions
Tung Mai and Vijay Vazirani. Finding Stable Matchings that are Robust to Errors in the Input
Hill Darryl, Nicolas Bonichon, Prosenjit Bose, Jean-Lou De Carufel, Vincent Despre and Michiel Smid. Improved Routing on the Delaunay Triangulation
Bo Zhou, Yi-Jen Chiang and Chee Yap. Soft Subdivision Motion Planning for Complex Planar Robots
Amos Fiat, Alon Eden, Michal Feldman and Tzahi Taub. Truthful Prompt Scheduling for Minimizing Sum of Completion Times
Isaac B. Goldstein, Moshe Lewenstein and Ely Porat. Improved Space-Time Tradeoffs for kSUM
Yun Kuen Cheung and Richard Cole. Amortized Analysis of Asynchronous Price Dynamics
Xiaoyu He, Neng Huang and Xiaoming Sun. On the Decision Tree Complexity of String Matching
Viatcheslav Korenwein, André Nichterlein, Rolf Niedermeier and Philipp Zschoche. Data Reduction for Maximum Matching on Sparse Graphs: Theory and Experiments
Giorgio Lucarelli, Benjamin Moseley, Kim Thang Nguyen, Abhinav Srivastav and Denis Trystram. Online Non-Preemptive Scheduling to Minimize Weighted Flow-time on Unrelated Machines
Waldo Gálvez, José A. Soto and José Verschae. Symmetry exploitation for Online Machine Covering with Bounded Migration
Arnold Filtser and Ofer Neiman. Light Spanners for High Dimensional Norms via Stochastic Decompositions
Amihood Amir, Gad M. Landau, Shoshana Marcus and Dina Sokol. Two-Dimensional Maximal Repetitions
Phani Raj Lolakapuri and Umang Bhaskar. Equilibrium Computation in Atomic Splittable Routing Games with Convex Cost Functions
Markus Chimani and Tilo Wiedera. Cycles to the Rescue! Novel Constraints to Compute Maximum Planar Subgraphs Fast
Dimitrios Gkenosis, Nathaniel Grammel, Lisa Hellerstein and Devorah Kletenik. Minimizing Classification Cost for Linear Scoring Functions
Mayank Goswami, Dzejla Medjedovic, Emina Mekic and Prashant Pandey. Buffered Count-Min Sketch on SSD: Theory and Experiments
Michał Gańczorz, Pawel Gawrychowski, Artur Jeż and Tomasz Kociumaka. Edit Distance with Block Operations
Michael Jarret, Stacey Jeffery, Shelby Kimmel and Alvaro Piedrafita. Quantum Algorithms for Connectivity and Related Problems
Steven Chaplick, Minati De, Alexander Ravsky and Joachim Spoerhase. Approximation Schemes for Geometric Coverage Problems
T-H. Hubert Chan, Haotian Jiang and Shaofeng H.-C. Jiang. A Unified PTAS for Prize Collecting TSP and Steiner Tree Problem in Doubling Metrics

ALGO program

Please see the ALGO 2018 web pages for more information on ALGO keynote speakers and social program.