ESA 2016 August 22-24, 2016 - Aarhus, Denmark

24th Annual European Symposium on Algorithms (ESA 2016)



Piotr Sankowski and Christos Zaroliagis (Eds.)
ISBN 978-3-95977-015-6, LIPICS Vol. 57 ISSN 1868-8969
Additional Information
License
Conference Website
Complete volume (PDF, 51 MB)
Search Publication Server


Authors
  • Ó Catháin, Padraig
  • Abolhassani, Melika
  • Abrahamsen, Mikkel
  • Alstrup, Stephen
  • Arndt, Tobias
  • Böhm, Martin
  • Basu Roy, Aniket
  • Baum, Moritz
  • Bei, Xiaohui
  • Bennett, Huck
  • Berenbrink, Petra
  • Bhattacharyya, Arnab
  • Bienkowski, Marcin
  • Bilo, Davide
  • Bläsius, Thomas
  • Blelloch, Guy E.
  • Bodwin, Greg
  • Bonnet, Édouard
  • Borassi, Michele
  • Borndörfer, Ralf
  • Bouts, Quirijn W.
  • Bringmann, Karl
  • Brubach, Brian
  • Byrka, Jaroslaw
  • Cardinal, Jean
  • Chalk, Cameron
  • Chambers, Erin
  • Chan, T.-H. Hubert
  • Chao, Megan
  • Chatterjee, Krishnendu
  • Chen, Fei
  • Chimani, Markus
  • Christodoulou, George
  • Chrobak, Marek
  • Clifford, Raphaël
  • Crouch, Michael
  • Curticapean, Radu
  • Dürr, Christoph
  • Dadush, Daniel
  • Dahlgaard, Sřren
  • De Carufel, Jean-Lou
  • de Rougemont, Michel
  • Dey, Tamal K.
  • Drucker, Andrew
  • Edelkamp, Stefan
  • Egri, László
  • Eiben, Eduard
  • Esfandiari, Hossein
  • Even, Guy
  • Feldman, Moran
  • Fineman, Jeremy T.
  • Fleszar, Krzysztof
  • Folwarczny, Lukas
  • François, Nathanaël
  • Friedetzky, Tom
  • Friedrich, Tobias
  • Gadekar, Ameet
  • Gairing, Martin
  • Ganian, Robert
  • Garg, Jugal
  • Gemsa, Andreas
  • Georgiadis, Loukas
  • Ghoshal, Suprovat
  • Gibbons, Phillip B.
  • Golan, Shay
  • Goldstein, Isaac
  • Goranci, Gramoz
  • Govindarajan, Sathish
  • Gu, Yan
  • Guala, Luciano
  • Hafner, Danijar
  • Hajiaghayi, MohammadTaghi
  • Halperin, Dan
  • Hamid, Mahini
  • Henzinger, Monika
  • Hoefer, Martin
  • Hoppmann, Heide
  • Huang, Chien-Chung
  • Huang, Lingxiao
  • Iacono, John
  • Irina Kostitsyna, Irina
  • Italiano, Giuseppe F.
  • Ito, Hiro
  • Jalsenius, Markus
  • Jez, Lukasz
  • Kärkkäinen, Juha
  • Kanga, Kustaa
  • Karbstein, Marika
  • Karppa, Matti
  • Kaski, Petteri
  • Katz, Matthew J.
  • Kejlberg-Rasmussen, Casper
  • Kellermeier, Thomas
  • Kempa, Dominik
  • Kesselheim, Thomas
  • Khot, Subhash
  • Khuller, Samir
  • Kim Thang, Nguyen
  • Kliemann, Lasse
  • Kling, Peter
  • Knudsen, Mathias Bćk Tejs
  • Kohonen, Jukka
  • Kolev, Pavel
  • Konrad, Christian
  • Kopelowitz, Tsvi
  • Korman, Matias
  • Kostitsyna, Irina
  • Kowalik, Lukasz
  • Kozma, László
  • Kratsch, Stefan
  • Krejca, Martin S.
  • Krinninger, Sebastian
  • Krogmann, Simon
  • Krohmer, Anton
  • Kunysz, Adam
  • Löffler, Maarten
  • Laue, Sören
  • Lauri, Juho
  • Leucci, Stefano
  • Lewenstein, Moshe
  • Li, Jian
  • Lucarelli, Giorgio
  • Magniez, Frédéric
  • Mallmann-Trenn, Frederik
  • Maria, Clément
  • Martinez, Eric
  • Marx, Dániel
  • McGregor, Andrew
  • Medina, Moti
  • Mehlhorn, Kurt
  • Mehta, Ruta
  • Meulemans, Wouter
  • Miltzow, Tillmann
  • Mnich, Matthias
  • Moran, Shay
  • Murray, Riley
  • Narayanaswamy, N. S.
  • Narins, Lothar
  • Natale, Emanuele
  • Nederlof, Jesper
  • Neuen, Daniel
  • Neumann, Stefan
  • Newman, Alantha
  • Nikoletseas, Sotiris
  • Okamoto, Yoshio
  • Ooms, Aurélien
  • Ordyniak, Sebastian
  • Ott, Sebastian
  • Panageas, Ioannis
  • Parotsidis, Nikos
  • Pavlogiannis, Andreas
  • Pettie, Seth
  • Phillips, Jeff M.
  • Piliouras, Georgios
  • Porat, Ely
  • Proietti, Guido
  • Röglin, Heiko
  • Raman, Rajiv
  • Raptopoulos, Christoforos
  • Rasmus Ibsen-Jensen, Rasmus
  • Rawitz, Dror
  • Ray, Saurabh
  • Razmjou, Armin
  • Renault, Marc
  • Roeloffzen, Marcel
  • Rosén, Adi
  • Rote, Günter
  • Rothenberger, Ralf
  • Roughgarden, Tim
  • Rutter, Ignaz
  • Sach, Benjamin
  • Saket, Rishi
  • Sankararaman, Karthik Abinav
  • Sankowski, Piotr
  • Santhanam, Rahul
  • Schielke, Christian
  • Schulz, Andreas S.
  • Schweller, Robert
  • Schwiegelshohn, Chris
  • Schwiegelshohn, Uwe
  • Seif, Johanna
  • Serre, Olivier
  • Sgall, Jiri
  • Shahbazian, Eduard
  • Shi, Dayu
  • Shun, Julian
  • Smorodinsky, Shakhar
  • Socala, Arkadiusz
  • Solovey, Kiril
  • Sonke, Willem
  • Spirakis, Paul
  • Spoerhase, Joachim
  • Spreer, Jonathan
  • Srinivasan, Aravind
  • Srivastav, Abhinav
  • Srivastav, Anand
  • Staals, Frank
  • Stephens-Davidowitz, Noah
  • Svensson, Ola
  • Tönnis, Andreas
  • Tennenholtz, Moshe
  • Thomas, Antonis
  • Thorup, Mikkel
  • Tov, Roei
  • Trystram, Denis
  • Uno, Takeaki
  • Végh, László A.
  • Valiant, Gregory
  • van Kreveld, Marc
  • van Renssen, André
  • Vassilevska Williams, Virginia
  • Vega, Luis
  • Verbeek, Kevin
  • Verschae, José
  • Vesely, Pavel
  • Walczak, Bartosz
  • Wang, Haitao
  • Wang, Joshua R.
  • Wang, Yusu
  • Wastell, Chris
  • Wegner, Franziska
  • Weinstein, Omri
  • Weiss, Armin
  • Wiedera, Tilo
  • Winslow, Andrew
  • Woodruff, David P.
  • Wu, Xiaowei
  • Wylie, Tim
  • Xu, Pan
  • Yazdanbod, Sadra
  • Zaroliagis, Christos
  • Zhan, Wei

  •   
    Front Matter, Table of Contents, Preface, Programm Commitee, External Reviewers
    Authors: Sankowski, Piotr ; Zaroliagis, Christos

    Abstract | Document (379 KB) | BibTeX

    2-Connectivity in Directed Graphs (Invited Talk)
    Authors: Georgiadis, Loukas ; Italiano, Giuseppe F. ; Parotsidis, Nikos

    Abstract | Document (1,442 KB) | BibTeX

    Algorithms with Provable Guarantees for Clustering (Invited Talk)
    Authors: Svensson, Ola

    Abstract | Document (201 KB) | BibTeX

    Beating Ratio 0.5 for Weighted Oblivious Matching Problems
    Authors: Abolhassani, Melika ; Chan, T.-H. Hubert ; Chen, Fei ; Esfandiari, Hossein ; Hajiaghayi, MohammadTaghi ; Hamid, Mahini ; Wu, Xiaowei

    Abstract | Document (618 KB) | BibTeX

    Outer Common Tangents and Nesting of Convex Hulls in Linear Time and Constant Workspace
    Authors: Abrahamsen, Mikkel ; Walczak, Bartosz

    Abstract | Document (526 KB) | BibTeX

    Sublinear Distance Labeling
    Authors: Alstrup, Stephen ; Dahlgaard, Sřren ; Knudsen, Mathias Bćk Tejs ; Porat, Ely

    Abstract | Document (578 KB) | BibTeX

    Probabilistic Routing for On-Street Parking Search
    Authors: Arndt, Tobias ; Hafner, Danijar ; Kellermeier, Thomas ; Krogmann, Simon ; Razmjou, Armin ; Krejca, Martin S. ; Rothenberger, Ralf ; Friedrich, Tobias

    Abstract | Document (5,164 KB) | BibTeX

    Scalable Exact Visualization of Isocontours in Road Networks via Minimum-Link Paths
    Authors: Baum, Moritz ; Bläsius, Thomas ; Gemsa, Andreas ; Rutter, Ignaz ; Wegner, Franziska

    Abstract | Document (2,074 KB) | BibTeX

    Computing Equilibria in Markets with Budget-Additive Utilities
    Authors: Bei, Xiaohui ; Garg, Jugal ; Hoefer, Martin ; Mehlhorn, Kurt

    Abstract | Document (436 KB) | BibTeX

    On the Lattice Distortion Problem
    Authors: Bennett, Huck ; Dadush, Daniel ; Stephens-Davidowitz, Noah

    Abstract | Document (620 KB) | BibTeX

    Plurality Consensus in Arbitrary Graphs: Lessons Learned from Load Balancing
    Authors: Berenbrink, Petra ; Friedetzky, Tom ; Kling, Peter ; Mallmann-Trenn, Frederik ; Wastell, Chris

    Abstract | Document (708 KB) | BibTeX

    On the Hardness of Learning Sparse Parities
    Authors: Bhattacharyya, Arnab ; Gadekar, Ameet ; Ghoshal, Suprovat ; Saket, Rishi

    Abstract | Document (655 KB) | BibTeX

    Online Algorithms for Multi-Level Aggregation
    Authors: Bienkowski, Marcin ; Böhm, Martin ; Byrka, Jaroslaw ; Chrobak, Marek ; Dürr, Christoph ; Folwarczny, Lukas ; Jez, Lukasz ; Sgall, Jiri ; Kim Thang, Nguyen ; Vesely, Pavel

    Abstract | Document (588 KB) | BibTeX

    Compact and Fast Sensitivity Oracles for Single-Source Distances
    Authors: Bilo, Davide ; Guala, Luciano ; Leucci, Stefano ; Proietti, Guido

    Abstract | Document (624 KB) | BibTeX

    Efficient Algorithms with Asymmetric Read and Write Costs
    Authors: Blelloch, Guy E. ; Fineman, Jeremy T. ; Gibbons, Phillip B. ; Gu, Yan ; Shun, Julian

    Abstract | Document (650 KB) | BibTeX

    Hyperbolic Random Graphs: Separators and Treewidth
    Authors: Bläsius, Thomas ; Friedrich, Tobias ; Krohmer, Anton

    Abstract | Document (567 KB) | BibTeX

    Efficient Embedding of Scale-Free Graphs in the Hyperbolic Plane
    Authors: Bläsius, Thomas ; Friedrich, Tobias ; Krohmer, Anton ; Laue, Sören

    Abstract | Document (3,332 KB) | BibTeX

    Fully Dynamic Spanners with Worst-Case Update Time
    Authors: Bodwin, Greg ; Krinninger, Sebastian

    Abstract | Document (530 KB) | BibTeX

    Fixed-Parameter Approximability of Boolean MinCSPs
    Authors: Bonnet, Édouard ; Egri, László ; Marx, Dániel

    Abstract | Document (1,218 KB) | BibTeX

    Parameterized Hardness of Art Gallery Problems
    Authors: Bonnet, Édouard ; Miltzow, Tillmann

    Abstract | Document (689 KB) | BibTeX

    KADABRA is an ADaptive Algorithm for Betweenness via Random Approximation
    Authors: Borassi, Michele ; Natale, Emanuele

    Abstract | Document (710 KB) | BibTeX

    Separation of Cycle Inequalities for the Periodic Timetabling Problem
    Authors: Borndörfer, Ralf ; Hoppmann, Heide ; Karbstein, Marika

    Abstract | Document (485 KB) | BibTeX

    Mapping Polygons to the Grid with Small Hausdorff and Fréchet Distance
    Authors: Bouts, Quirijn W. ; Irina Kostitsyna, Irina ; van Kreveld, Marc ; Meulemans, Wouter ; Sonke, Willem ; Verbeek, Kevin

    Abstract | Document (671 KB) | BibTeX

    Hitting Set for Hypergraphs of Low VC-dimension
    Authors: Bringmann, Karl ; Kozma, László ; Moran, Shay ; Narayanaswamy, N. S.

    Abstract | Document (658 KB) | BibTeX

    New Algorithms, Better Bounds, and a Novel Model for Online Stochastic Matching
    Authors: Brubach, Brian ; Sankararaman, Karthik Abinav ; Srinivasan, Aravind ; Xu, Pan

    Abstract | Document (605 KB) | BibTeX

    Solving k-SUM Using Few Linear Queries
    Authors: Cardinal, Jean ; Iacono, John ; Ooms, Aurélien

    Abstract | Document (572 KB) | BibTeX

    Optimal Staged Self-Assembly of General Shapes
    Authors: Chalk, Cameron ; Martinez, Eric ; Schweller, Robert ; Vega, Luis ; Winslow, Andrew ; Wylie, Tim

    Abstract | Document (970 KB) | BibTeX

    Homotopy Measures for Representative Trajectories
    Authors: Chambers, Erin ; Kostitsyna, Irina ; Löffler, Maarten ; Staals, Frank

    Abstract | Document (1,029 KB) | BibTeX

    Optimal Reachability and a Space-Time Tradeoff for Distance Queries in Constant-Treewidth Graphs
    Authors: Chatterjee, Krishnendu ; Rasmus Ibsen-Jensen, Rasmus ; Pavlogiannis, Andreas

    Abstract | Document (566 KB) | BibTeX

    An ILP-based Proof System for the Crossing Number Problem
    Authors: Chimani, Markus ; Wiedera, Tilo

    Abstract | Document (468 KB) | BibTeX

    Strategic Contention Resolution with Limited Feedback
    Authors: Christodoulou, George ; Gairing, Martin ; Nikoletseas, Sotiris ; Raptopoulos, Christoforos ; Spirakis, Paul

    Abstract | Document (537 KB) | BibTeX

    Cell-Probe Lower Bounds for Bit Stream Computation
    Authors: Clifford, Raphaël ; Jalsenius, Markus ; Sach, Benjamin

    Abstract | Document (586 KB) | BibTeX

    Stochastic Streams: Sample Complexity vs. Space Complexity
    Authors: Crouch, Michael ; McGregor, Andrew ; Valiant, Gregory ; Woodruff, David P.

    Abstract | Document (489 KB) | BibTeX

    Counting Matchings with k Unmatched Vertices in Planar Graphs
    Authors: Curticapean, Radu

    Abstract | Document (609 KB) | BibTeX

    On Interference Among Moving Sensors and Related Problems
    Authors: De Carufel, Jean-Lou ; Katz, Matthew J. ; Korman, Matias ; van Renssen, André ; Roeloffzen, Marcel ; Smorodinsky, Shakhar

    Abstract | Document (496 KB) | BibTeX

    SimBa: An Efficient Tool for Approximating Rips-Filtration Persistence via Simplicial Batch-Collapse
    Authors: Dey, Tamal K. ; Shi, Dayu ; Wang, Yusu

    Abstract | Document (1,691 KB) | BibTeX

    Exponential Time Paradigms Through the Polynomial Time Lens
    Authors: Drucker, Andrew ; Nederlof, Jesper ; Santhanam, Rahul

    Abstract | Document (566 KB) | BibTeX

    On the Power of Advice and Randomization for Online Bipartite Matching
    Authors: Dürr, Christoph ; Konrad, Christian ; Renault, Marc

    Abstract | Document (643 KB) | BibTeX

    BlockQuicksort: Avoiding Branch Mispredictions in Quicksort
    Authors: Edelkamp, Stefan ; Weiss, Armin

    Abstract | Document (622 KB) | BibTeX

    Counting Linear Extensions: Parameterizations by Treewidth
    Authors: Eiben, Eduard ; Ganian, Robert ; Kanga, Kustaa ; Ordyniak, Sebastian

    Abstract | Document (635 KB) | BibTeX

    A Constant Approximation Algorithm for Scheduling Packets on Line Networks
    Authors: Even, Guy ; Medina, Moti ; Rosén, Adi

    Abstract | Document (684 KB) | BibTeX

    Distributed Signaling Games
    Authors: Feldman, Moran ; Tennenholtz, Moshe ; Weinstein, Omri

    Abstract | Document (589 KB) | BibTeX

    New Algorithms for Maximum Disjoint Paths Based on Tree-Likeness
    Authors: Fleszar, Krzysztof ; Mnich, Matthias ; Spoerhase, Joachim

    Abstract | Document (611 KB) | BibTeX

    Streaming Property Testing of Visibly Pushdown Languages
    Authors: François, Nathanaël ; Magniez, Frédéric ; de Rougemont, Michel ; Serre, Olivier

    Abstract | Document (682 KB) | BibTeX

    Streaming Pattern Matching with d Wildcards
    Authors: Golan, Shay ; Kopelowitz, Tsvi ; Porat, Ely

    Abstract | Document (1,145 KB) | BibTeX

    How Hard is it to Find (Honest) Witnesses?
    Authors: Goldstein, Isaac ; Kopelowitz, Tsvi ; Lewenstein, Moshe ; Porat, Ely

    Abstract | Document (558 KB) | BibTeX

    Incremental Exact Min-Cut in Poly-logarithmic Amortized Update Time
    Authors: Goranci, Gramoz ; Henzinger, Monika ; Thorup, Mikkel

    Abstract | Document (534 KB) | BibTeX

    Packing and Covering with Non-Piercing Regions
    Authors: Govindarajan, Sathish ; Raman, Rajiv ; Ray, Saurabh ; Basu Roy, Aniket

    Abstract | Document (519 KB) | BibTeX

    Incremental and Fully Dynamic Subgraph Connectivity For Emergency Planning
    Authors: Henzinger, Monika ; Neumann, Stefan

    Abstract | Document (423 KB) | BibTeX

    A Combinatorial Approximation Algorithm for Graph Balancing with Light Hyper Edges
    Authors: Huang, Chien-Chung ; Ott, Sebastian

    Abstract | Document (532 KB) | BibTeX

    epsilon-Kernel Coresets for Stochastic Points
    Authors: Huang, Lingxiao ; Li, Jian ; Phillips, Jeff M. ; Wang, Haitao

    Abstract | Document (661 KB) | BibTeX

    Every Property Is Testable on a Natural Class of Scale-Free Multigraphs
    Authors: Ito, Hiro

    Abstract | Document (505 KB) | BibTeX

    Explicit Correlation Amplifiers for Finding Outlier Correlations in Deterministic Subquadratic Time
    Authors: Karppa, Matti ; Kaski, Petteri ; Kohonen, Jukka ; Ó Catháin, Padraig

    Abstract | Document (593 KB) | BibTeX

    Faster Worst Case Deterministic Dynamic Connectivity
    Authors: Kejlberg-Rasmussen, Casper ; Kopelowitz, Tsvi ; Pettie, Seth ; Thorup, Mikkel

    Abstract | Document (597 KB) | BibTeX

    Think Eternally: Improved Algorithms for the Temp Secretary Problem and Extensions
    Authors: Kesselheim, Thomas ; Tönnis, Andreas

    Abstract | Document (546 KB) | BibTeX

    Hardness of Bipartite Expansion
    Authors: Khot, Subhash ; Saket, Rishi

    Abstract | Document (519 KB) | BibTeX

    A Streaming Algorithm for the Undirected Longest Path Problem
    Authors: Kliemann, Lasse ; Schielke, Christian ; Srivastav, Anand

    Abstract | Document (613 KB) | BibTeX

    A Note On Spectral Clustering
    Authors: Kolev, Pavel ; Mehlhorn, Kurt

    Abstract | Document (581 KB) | BibTeX

    On the Fine-Grained Complexity of Rainbow Coloring
    Authors: Kowalik, Lukasz ; Lauri, Juho ; Socala, Arkadiusz

    Abstract | Document (681 KB) | BibTeX

    A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter
    Authors: Kratsch, Stefan

    Abstract | Document (545 KB) | BibTeX

    The Strongly Stable Roommates Problem
    Authors: Kunysz, Adam

    Abstract | Document (526 KB) | BibTeX

    Faster External Memory LCP Array Construction
    Authors: Kärkkäinen, Juha ; Kempa, Dominik

    Abstract | Document (685 KB) | BibTeX

    Almost All Even Yao-Yao Graphs Are Spanners
    Authors: Li, Jian ; Zhan, Wei

    Abstract | Document (625 KB) | BibTeX

    Online Non-Preemptive Scheduling in a Resource Augmentation Model Based on Duality
    Authors: Lucarelli, Giorgio ; Kim Thang, Nguyen ; Srivastav, Abhinav ; Trystram, Denis

    Abstract | Document (479 KB) | BibTeX

    Admissible Colourings of 3-Manifold Triangulations for Turaev-Viro Type Invariants
    Authors: Maria, Clément ; Spreer, Jonathan

    Abstract | Document (1,356 KB) | BibTeX

    The Computational Complexity of Genetic Diversity
    Authors: Mehta, Ruta ; Panageas, Ioannis ; Piliouras, Georgios ; Yazdanbod, Sadra

    Abstract | Document (621 KB) | BibTeX

    Approximation and Hardness of Token Swapping
    Authors: Miltzow, Tillmann ; Narins, Lothar ; Okamoto, Yoshio ; Rote, Günter ; Thomas, Antonis ; Uno, Takeaki

    Abstract | Document (532 KB) | BibTeX

    A 7/3-Approximation for Feedback Vertex Sets in Tournaments
    Authors: Mnich, Matthias ; Vassilevska Williams, Virginia ; Végh, László A.

    Abstract | Document (598 KB) | BibTeX

    Scheduling Distributed Clusters of Parallel Machines: Primal-Dual and LP-based Approximation Algorithms
    Authors: Murray, Riley ; Chao, Megan ; Khuller, Samir

    Abstract | Document (594 KB) | BibTeX

    Finding Large Set Covers Faster via the Representation Method
    Authors: Nederlof, Jesper

    Abstract | Document (550 KB) | BibTeX

    Graph Isomorphism for Unit Square Graphs
    Authors: Neuen, Daniel

    Abstract | Document (539 KB) | BibTeX

    The Alternating Stock Size Problem and the Gasoline Puzzle
    Authors: Newman, Alantha ; Röglin, Heiko ; Seif, Johanna

    Abstract | Document (515 KB) | BibTeX

    New Parameterized Algorithms for APSP in Directed Graphs
    Authors: Porat, Ely ; Shahbazian, Eduard ; Tov, Roei

    Abstract | Document (493 KB) | BibTeX

    Online Budgeted Maximum Coverage
    Authors: Rawitz, Dror ; Rosén, Adi

    Abstract | Document (547 KB) | BibTeX

    Min-Sum Scheduling Under Precedence Constraints
    Authors: Schulz, Andreas S. ; Verschae, José

    Abstract | Document (510 KB) | BibTeX

    The Power of Migration for Online Slack Scheduling
    Authors: Schwiegelshohn, Chris ; Schwiegelshohn, Uwe

    Abstract | Document (545 KB) | BibTeX

    Sampling-Based Bottleneck Pathfinding with Applications to Fréchet Matching
    Authors: Solovey, Kiril ; Halperin, Dan

    Abstract | Document (653 KB) | BibTeX

    On the Geodesic Centers of Polygonal Domains
    Authors: Wang, Haitao

    Abstract | Document (567 KB) | BibTeX

    The Complexity of the k-means Method
    Authors: Roughgarden, Tim ; Wang, Joshua R.

    Abstract | Document (499 KB) | BibTeX

      




    DROPS-Home | Fulltext Search | Imprint Published by LZI