ESA 2018 August 20-22, 2018 - Helsinki, Finland

26th Annual European Symposium on Algorithms (ESA 2018)



Yossi Azar and Hannah Bast and Grzegorz Herman (Eds.)
ISBN 978-3-95977-081-1, LIPICS Vol. 112 ISSN 1868-8969
Additional Information
License
Conference Website
Complete volume (PDF, 35 MB)
Search Publication Server


Authors
  • Ahmadian, Sara
  • Amir, Amihood
  • Arya, Sunil
  • Auger, Nicolas
  • Azar, Yossi
  • Békési, József
  • Bader, David A.
  • Balogh, János
  • Bannach, Max
  • Bast, Hannah
  • Becchetti, Luca
  • Becker, Amariah
  • Bergamini, Elisabetta
  • Berndt, Sebastian
  • Bhaskar, Umang
  • Blelloch, Guy E.
  • Boczkowski, Lucas
  • Boissonnat, Jean-Daniel
  • Bonichon, Nicolas
  • Bose, Prosenjit
  • Brandt, Sebastian
  • Cao, Yixin
  • Carstens, Corrie Jacobien
  • Chakraborty, Diptarka
  • Chakraborty, Sankardeep
  • Chalk, Cameron
  • Chan, T-H. Hubert
  • Chang, Hsien-Chih
  • Chaplick, Steven
  • Cheung, Yun Kuen
  • Chiang, Yi-Jen
  • Chimani, Markus
  • Chitnis, Rajesh
  • Clementi, Andrea
  • Cole, Richard
  • Cygan, Marek
  • Czumaj, Artur
  • Dósa, György
  • da Fonseca, Guilherme D.
  • Das, Debarati
  • De, Minati
  • De Carufel, Jean-Lou
  • Despré, Vincent
  • Ding, Hu
  • Dinitz, Michael
  • Dorfman, Dani
  • Eden, Alon
  • El-Zein, Hicham
  • Englert, Matthias
  • Epstein, Leah
  • Feldman, Michal
  • Feldmann, Andreas Emil
  • Fiat, Amos
  • Fichte, Johannes K.
  • Filtser, Arnold
  • Fomin, Fedor V.
  • Gálvez, Waldo
  • Ganczorz, Michal
  • Garg, Shilpa
  • Gawrychowski, Pawel
  • Ghosh, Arijit
  • Gkenosis, Dimitrios
  • Goldstein, Isaac
  • Golin, Mordecai
  • Golovach, Petr A.
  • Goranci, Gramoz
  • Goswami, Mayank
  • Grammel, Nathaniel
  • Green, Oded
  • Grossi, Roberto
  • Gu, Yan
  • Hamann, Michael
  • He, Meng
  • He, Xiaoyu
  • Hecher, Markus
  • Hellerstein, Lisa
  • Henzinger, Monika
  • Herman, Grzegorz
  • Hill, Darryl
  • Holm, Jacob
  • Huang, Neng
  • Iacono, John
  • Italiano, Giuseppe F.
  • Ivanyos, Gábor
  • Jansen, Bart M. P.
  • Jarret, Michael
  • Jeffery, Stacey
  • Jelínek, Vít
  • Jez, Artur
  • Jiang, Haotian
  • Jiang, Shaofeng H.-C.
  • Jugé, Vincent
  • Künnemann, Marvin
  • Kanj, Iyad
  • Kaplan, Haim
  • Karczmarz, Adam
  • Kempa, Dominik
  • Kimmel, Shelby
  • Klein, Philip N.
  • Kletenik, Devorah
  • Kociumaka, Tomasz
  • Kolay, Sudeshna
  • Komusiewicz, Christian
  • Korenwein, Viatcheslav
  • Korman, Amos
  • Koucký, Michal
  • Kozma, László
  • Kratsch, Stefan
  • Lacki, Jakub
  • Landau, Gad M.
  • Langerman, Stefan
  • Lee, Euiwoong
  • Leniowski, Dariusz
  • Levin, Asaf
  • Lewenstein, Moshe
  • Liu, Manni
  • Lolakapuri, Phani Raj
  • Lucarelli, Giorgio
  • Luchsinger, Austin
  • Mömke, Tobias
  • Mai, Tung
  • Manurangsi, Pasin
  • Marcus, Shoshana
  • Margot, François
  • Martin, Barnaby
  • Matheny, Michael
  • Medjedovic, Dzejla
  • Mekic, Emina
  • Meyer, Ulrich
  • Meyerhenke, Henning
  • Mezlaf, David
  • Mishra, Gopinath
  • Moseley, Benjamin
  • Mount, David M.
  • Mozes, Shay
  • Mucha, Marcin
  • Mukherjee, Anish
  • Munro, J. Ian
  • Mustafa, Nabil H.
  • Natale, Emanuele
  • Nederlof, Jesper
  • Neiman, Ofer
  • Nekrich, Yakov
  • Nelles, Florian
  • Nicaud, Cyril
  • Nichterlein, André
  • Niedermeier, Rolf
  • Opler, Michal
  • Pandey, Prashant
  • Panolan, Fahad
  • Pareek, Divyansh
  • Pasquale, Francesco
  • Paulusma, Daniël
  • Peng, Pan
  • Penschuck, Manuel
  • Pettie, Seth
  • Phillips, Jeff M.
  • Piedrafita, Alvaro
  • Pieterse, Astrid
  • Pilipczuk, Michal
  • Pivoteau, Carine
  • Policriti, Alberto
  • Porat, Ely
  • Prakash, Anupam
  • Prezza, Nicola
  • Pritam, Siddharth
  • Probst, Maximilian
  • Raghavendra, Prasad
  • Rai, Ashutosh
  • Raman, Rajiv
  • Raman, Venkatesh
  • Ramanujan, M. S.
  • Ravsky, Alexander
  • Ray, Saurabh
  • Raymond, Jean-Florent
  • Rodeh, Yoav
  • Rotenberg, Eva
  • Sandeep, R. B.
  • Sandlund, Bryce
  • Sanitŕ, Laura
  • Sankowski, Piotr
  • Santha, Miklos
  • Satti, Srinivasa Rao
  • Saulpic, David
  • Saurabh, Nitin
  • Saurabh, Saket
  • Schapira, Michael
  • Schmidt, Daniel R.
  • Schweller, Robert
  • Shahaf, Gal
  • Singla, Sahil
  • Smid, Michiel
  • Sokol, Dina
  • Solomon, Shay
  • Sorge, Manuel
  • Soto, José A.
  • Spoerhase, Joachim
  • Srivastav, Abhinav
  • Sun, Xiaoming
  • Sun, Yihan
  • Swamy, Chaitanya
  • Taub, Tzahi
  • Thang, Nguyen Kim
  • Tran, Hung
  • Trevisan, Luca
  • Trystram, Denis
  • Uitto, Jara
  • Valtr, Pavel
  • van der Grinten, Alexander
  • van Leeuwen, Erik Jan
  • Vazirani, Vijay V.
  • Versari, Luca
  • Verschae, José
  • Wagner, Dorothea
  • Weimann, Oren
  • Wein, Nicole
  • Westermann, Matthias
  • Wiedera, Tilo
  • Wiese, Andreas
  • Wild, Sebastian
  • Woltran, Stefan
  • Wylie, Tim
  • Yap, Chee
  • Ye, Junjie
  • Zey, Bernd
  • Zhou, Bo
  • Zisser, Markus
  • Zschoche, Philipp
  • Zwick, Uri

  •   
    Front Matter, Table of Contents, Preface, Conference Organization
    Authors: Azar, Yossi ; Bast, Hannah ; Herman, Grzegorz

    Abstract | Document (332 KB) | BibTeX

    Algorithms for Inverse Optimization Problems
    Authors: Ahmadian, Sara ; Bhaskar, Umang ; Sanitŕ, Laura ; Swamy, Chaitanya

    Abstract | Document (495 KB) | BibTeX

    Two-Dimensional Maximal Repetitions
    Authors: Amir, Amihood ; Landau, Gad M. ; Marcus, Shoshana ; Sokol, Dina

    Abstract | Document (484 KB) | BibTeX

    Approximate Convex Intersection Detection with Applications to Width and Minkowski Sums
    Authors: Arya, Sunil ; da Fonseca, Guilherme D. ; Mount, David M.

    Abstract | Document (609 KB) | BibTeX

    On the Worst-Case Complexity of TimSort
    Authors: Auger, Nicolas ; Jugé, Vincent ; Nicaud, Cyril ; Pivoteau, Carine

    Abstract | Document (615 KB) | BibTeX

    A New and Improved Algorithm for Online Bin Packing
    Authors: Balogh, János ; Békési, József ; Dósa, György ; Epstein, Leah ; Levin, Asaf

    Abstract | Document (327 KB) | BibTeX

    Practical Access to Dynamic Programming on Tree Decompositions
    Authors: Bannach, Max ; Berndt, Sebastian

    Abstract | Document (651 KB) | BibTeX

    Average Whenever You Meet: Opportunistic Protocols for Community Detection
    Authors: Becchetti, Luca ; Clementi, Andrea ; Manurangsi, Pasin ; Natale, Emanuele ; Pasquale, Francesco ; Raghavendra, Prasad ; Trevisan, Luca

    Abstract | Document (543 KB) | BibTeX

    Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension
    Authors: Becker, Amariah ; Klein, Philip N. ; Saulpic, David

    Abstract | Document (866 KB) | BibTeX

    Fine-grained Lower Bounds on Cops and Robbers
    Authors: Brandt, Sebastian ; Pettie, Seth ; Uitto, Jara

    Abstract | Document (595 KB) | BibTeX

    A Polynomial Kernel for Diamond-Free Editing
    Authors: Cao, Yixin ; Rai, Ashutosh ; Sandeep, R. B. ; Ye, Junjie

    Abstract | Document (507 KB) | BibTeX

    Parallel and I/O-efficient Randomisation of Massive Networks using Global Curveball Trades
    Authors: Carstens, Corrie Jacobien ; Hamann, Michael ; Meyer, Ulrich ; Penschuck, Manuel ; Tran, Hung ; Wagner, Dorothea

    Abstract | Document (980 KB) | BibTeX

    Space-Optimal Quasi-Gray Codes with Logarithmic Read Complexity
    Authors: Chakraborty, Diptarka ; Das, Debarati ; Koucký, Michal ; Saurabh, Nitin

    Abstract | Document (474 KB) | BibTeX

    A Framework for In-place Graph Algorithms
    Authors: Chakraborty, Sankardeep ; Mukherjee, Anish ; Raman, Venkatesh ; Satti, Srinivasa Rao

    Abstract | Document (438 KB) | BibTeX

    Self-Assembly of Any Shape with Constant Tile Types using High Temperature
    Authors: Chalk, Cameron ; Luchsinger, Austin ; Schweller, Robert ; Wylie, Tim

    Abstract | Document (648 KB) | BibTeX

    A Unified PTAS for Prize Collecting TSP and Steiner Tree Problem in Doubling Metrics
    Authors: Chan, T-H. Hubert ; Jiang, Haotian ; Jiang, Shaofeng H.-C.

    Abstract | Document (526 KB) | BibTeX

    Near-Optimal Distance Emulator for Planar Graphs
    Authors: Chang, Hsien-Chih ; Gawrychowski, Pawel ; Mozes, Shay ; Weimann, Oren

    Abstract | Document (525 KB) | BibTeX

    Approximation Schemes for Geometric Coverage Problems
    Authors: Chaplick, Steven ; De, Minati ; Ravsky, Alexander ; Spoerhase, Joachim

    Abstract | Document (564 KB) | BibTeX

    Amortized Analysis of Asynchronous Price Dynamics
    Authors: Cheung, Yun Kuen ; Cole, Richard

    Abstract | Document (513 KB) | BibTeX

    Cycles to the Rescue! Novel Constraints to Compute Maximum Planar Subgraphs Fast
    Authors: Chimani, Markus ; Wiedera, Tilo

    Abstract | Document (493 KB) | BibTeX

    Parameterized Approximation Algorithms for Bidirected Steiner Network Problems
    Authors: Chitnis, Rajesh ; Feldmann, Andreas Emil ; Manurangsi, Pasin

    Abstract | Document (533 KB) | BibTeX

    Online Facility Location with Deletions
    Authors: Cygan, Marek ; Czumaj, Artur ; Mucha, Marcin ; Sankowski, Piotr

    Abstract | Document (444 KB) | BibTeX

    Improved Routing on the Delaunay Triangulation
    Authors: Bonichon, Nicolas ; Bose, Prosenjit ; De Carufel, Jean-Lou ; Despré, Vincent ; Hill, Darryl ; Smid, Michiel

    Abstract | Document (1,369 KB) | BibTeX

    On Geometric Prototype and Applications
    Authors: Ding, Hu ; Liu, Manni

    Abstract | Document (634 KB) | BibTeX

    Improved Bounds for Multipass Pairing Heaps and Path-Balanced Binary Search Trees
    Authors: Dorfman, Dani ; Kaplan, Haim ; Kozma, László ; Pettie, Seth ; Zwick, Uri

    Abstract | Document (610 KB) | BibTeX

    Improved Time and Space Bounds for Dynamic Range Mode
    Authors: El-Zein, Hicham ; He, Meng ; Munro, J. Ian ; Sandlund, Bryce

    Abstract | Document (476 KB) | BibTeX

    Online Makespan Scheduling with Job Migration on Uniform Machines
    Authors: Englert, Matthias ; Mezlaf, David ; Westermann, Matthias

    Abstract | Document (382 KB) | BibTeX

    Truthful Prompt Scheduling for Minimizing Sum of Completion Times
    Authors: Eden, Alon ; Feldman, Michal ; Fiat, Amos ; Taub, Tzahi

    Abstract | Document (616 KB) | BibTeX

    Weighted Model Counting on the GPU by Exploiting Small Treewidth
    Authors: Fichte, Johannes K. ; Hecher, Markus ; Woltran, Stefan ; Zisser, Markus

    Abstract | Document (884 KB) | BibTeX

    Light Spanners for High Dimensional Norms via Stochastic Decompositions
    Authors: Filtser, Arnold ; Neiman, Ofer

    Abstract | Document (545 KB) | BibTeX

    On the Tractability of Optimization Problems on H-Graphs
    Authors: Fomin, Fedor V. ; Golovach, Petr A. ; Raymond, Jean-Florent

    Abstract | Document (538 KB) | BibTeX

    On the Optimality of Pseudo-polynomial Algorithms for Integer Programming
    Authors: Fomin, Fedor V. ; Panolan, Fahad ; Ramanujan, M. S. ; Saurabh, Saket

    Abstract | Document (436 KB) | BibTeX

    Symmetry Exploitation for Online Machine Covering with Bounded Migration
    Authors: Gálvez, Waldo ; Soto, José A. ; Verschae, José

    Abstract | Document (498 KB) | BibTeX

    Edit Distance with Block Operations
    Authors: Ganczorz, Michal ; Gawrychowski, Pawel ; Jez, Artur ; Kociumaka, Tomasz

    Abstract | Document (415 KB) | BibTeX

    A QPTAS for Gapless MEC
    Authors: Garg, Shilpa ; Mömke, Tobias

    Abstract | Document (495 KB) | BibTeX

    FPT Algorithms for Embedding into Low Complexity Graphic Metrics
    Authors: Ghosh, Arijit ; Kolay, Sudeshna ; Mishra, Gopinath

    Abstract | Document (499 KB) | BibTeX

    The Stochastic Score Classification Problem
    Authors: Gkenosis, Dimitrios ; Grammel, Nathaniel ; Hellerstein, Lisa ; Kletenik, Devorah

    Abstract | Document (488 KB) | BibTeX

    Improved Space-Time Tradeoffs for kSUM
    Authors: Goldstein, Isaac ; Lewenstein, Moshe ; Porat, Ely

    Abstract | Document (444 KB) | BibTeX

    Dynamic Trees with Almost-Optimal Access Cost
    Authors: Golin, Mordecai ; Iacono, John ; Langerman, Stefan ; Munro, J. Ian ; Nekrich, Yakov

    Abstract | Document (524 KB) | BibTeX

    A Tree Structure For Dynamic Facility Location
    Authors: Goranci, Gramoz ; Henzinger, Monika ; Leniowski, Dariusz

    Abstract | Document (477 KB) | BibTeX

    Dynamic Effective Resistances and Approximate Schur Complement on Separable Graphs
    Authors: Goranci, Gramoz ; Henzinger, Monika ; Peng, Pan

    Abstract | Document (537 KB) | BibTeX

    Buffered Count-Min Sketch on SSD: Theory and Experiments
    Authors: Goswami, Mayank ; Medjedovic, Dzejla ; Mekic, Emina ; Pandey, Prashant

    Abstract | Document (1,106 KB) | BibTeX

    Scalable Katz Ranking Computation in Large Static and Dynamic Graphs
    Authors: van der Grinten, Alexander ; Bergamini, Elisabetta ; Green, Oded ; Bader, David A. ; Meyerhenke, Henning

    Abstract | Document (548 KB) | BibTeX

    Round-Hashing for Data Storage: Distributed Servers and External-Memory Tables
    Authors: Grossi, Roberto ; Versari, Luca

    Abstract | Document (599 KB) | BibTeX

    Algorithmic Building Blocks for Asymmetric Memories
    Authors: Gu, Yan ; Sun, Yihan ; Blelloch, Guy E.

    Abstract | Document (586 KB) | BibTeX

    On the Decision Tree Complexity of String Matching
    Authors: He, Xiaoyu ; Huang, Neng ; Sun, Xiaoming

    Abstract | Document (443 KB) | BibTeX

    Decremental SPQR-trees for Planar Graphs
    Authors: Holm, Jacob ; Italiano, Giuseppe F. ; Karczmarz, Adam ; Lacki, Jakub ; Rotenberg, Eva

    Abstract | Document (508 KB) | BibTeX

    Computing the Chromatic Number Using Graph Decompositions via Matrix Rank
    Authors: Jansen, Bart M. P. ; Nederlof, Jesper

    Abstract | Document (533 KB) | BibTeX

    Polynomial Kernels for Hitting Forbidden Minors under Structural Parameterizations
    Authors: Jansen, Bart M. P. ; Pieterse, Astrid

    Abstract | Document (678 KB) | BibTeX

    Quantum Algorithms for Connectivity and Related Problems
    Authors: Jarret, Michael ; Jeffery, Stacey ; Kimmel, Shelby ; Piedrafita, Alvaro

    Abstract | Document (485 KB) | BibTeX

    Generalized Coloring of Permutations
    Authors: Jelínek, Vít ; Opler, Michal ; Valtr, Pavel

    Abstract | Document (495 KB) | BibTeX

    Solving Partition Problems Almost Always Requires Pushing Many Vertices Around
    Authors: Kanj, Iyad ; Komusiewicz, Christian ; Sorge, Manuel ; van Leeuwen, Erik Jan

    Abstract | Document (712 KB) | BibTeX

    String Attractors: Verification and Optimization
    Authors: Kempa, Dominik ; Policriti, Alberto ; Prezza, Nicola ; Rotenberg, Eva

    Abstract | Document (446 KB) | BibTeX

    Data Reduction for Maximum Matching on Real-World Graphs: Theory and Experiments
    Authors: Korenwein, Viatcheslav ; Nichterlein, André ; Niedermeier, Rolf ; Zschoche, Philipp

    Abstract | Document (498 KB) | BibTeX

    Searching a Tree with Permanently Noisy Advice
    Authors: Boczkowski, Lucas ; Korman, Amos ; Rodeh, Yoav

    Abstract | Document (524 KB) | BibTeX

    Efficient and Adaptive Parameterized Algorithms on Modular Decompositions
    Authors: Kratsch, Stefan ; Nelles, Florian

    Abstract | Document (521 KB) | BibTeX

    On Nondeterministic Derandomization of Freivalds' Algorithm: Consequences, Avenues and Algorithmic Progress
    Authors: Künnemann, Marvin

    Abstract | Document (527 KB) | BibTeX

    Optimal Online Contention Resolution Schemes via Ex-Ante Prophet Inequalities
    Authors: Lee, Euiwoong ; Singla, Sahil

    Abstract | Document (489 KB) | BibTeX

    Equilibrium Computation in Atomic Splittable Routing Games
    Authors: Bhaskar, Umang ; Lolakapuri, Phani Raj

    Abstract | Document (531 KB) | BibTeX

    Online Non-Preemptive Scheduling to Minimize Weighted Flow-time on Unrelated Machines
    Authors: Lucarelli, Giorgio ; Moseley, Benjamin ; Thang, Nguyen Kim ; Srivastav, Abhinav ; Trystram, Denis

    Abstract | Document (440 KB) | BibTeX

    Finding Stable Matchings That Are Robust to Errors in the Input
    Authors: Mai, Tung ; Vazirani, Vijay V.

    Abstract | Document (372 KB) | BibTeX

    Disconnected Cuts in Claw-free Graphs
    Authors: Martin, Barnaby ; Paulusma, Daniël ; van Leeuwen, Erik Jan

    Abstract | Document (441 KB) | BibTeX

    Practical Low-Dimensional Halfspace Range Space Sampling
    Authors: Matheny, Michael ; Phillips, Jeff M.

    Abstract | Document (641 KB) | BibTeX

    Nearly-Optimal Mergesorts: Fast, Practical Sorting Methods That Optimally Adapt to Existing Runs
    Authors: Munro, J. Ian ; Wild, Sebastian

    Abstract | Document (644 KB) | BibTeX

    On a Problem of Danzer
    Authors: Mustafa, Nabil H. ; Ray, Saurabh

    Abstract | Document (400 KB) | BibTeX

    Quasi-Polynomial Time Approximation Schemes for Packing and Covering Problems in Planar Graphs
    Authors: Pilipczuk, Michal ; van Leeuwen, Erik Jan ; Wiese, Andreas

    Abstract | Document (709 KB) | BibTeX

    On Learning Linear Functions from Subset and Its Applications in Quantum Computing
    Authors: Ivanyos, Gábor ; Prakash, Anupam ; Santha, Miklos

    Abstract | Document (434 KB) | BibTeX

    Strong Collapse for Persistence
    Authors: Boissonnat, Jean-Daniel ; Pritam, Siddharth ; Pareek, Divyansh

    Abstract | Document (491 KB) | BibTeX

    On the Complexity of the (Approximate) Nearest Colored Node Problem
    Authors: Probst, Maximilian

    Abstract | Document (633 KB) | BibTeX

    Planar Support for Non-piercing Regions and Applications
    Authors: Raman, Rajiv ; Ray, Saurabh

    Abstract | Document (666 KB) | BibTeX

    An Exact Algorithm for the Steiner Forest Problem
    Authors: Schmidt, Daniel R. ; Zey, Bernd ; Margot, François

    Abstract | Document (596 KB) | BibTeX

    Large Low-Diameter Graphs are Good Expanders
    Authors: Dinitz, Michael ; Schapira, Michael ; Shahaf, Gal

    Abstract | Document (548 KB) | BibTeX

    Improved Dynamic Graph Coloring
    Authors: Solomon, Shay ; Wein, Nicole

    Abstract | Document (434 KB) | BibTeX

    Soft Subdivision Motion Planning for Complex Planar Robots
    Authors: Zhou, Bo ; Chiang, Yi-Jen ; Yap, Chee

    Abstract | Document (867 KB) | BibTeX

      




    DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI