Portal - ESA 2016

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

Chatterjee, Krishnendu

Chen, Fei

Chimani, Markus

Christodoulou, George

Govindarajan, Sathish

Guala, Luciano

Gu, Yan

Hafner, Danijar

Hajiaghayi, MohammadTaghi

Irina Kostitsyna, Irina

Italiano, Giuseppe F.

Kejlberg-Rasmussen, Casper

Knudsen, Mathias Bæk Tejs

Krinninger, Sebastian

Mallmann-Trenn, Frederik

Pavlogiannis, Andreas

Raptopoulos, Christoforos

Rasmus Ibsen-Jensen, Rasmus

Sankararaman, Karthik Abinav

Schwiegelshohn, Chris

Stephens-Davidowitz, Noah

Vassilevska Williams, Virginia

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 ; Kangas, 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 | Privacy Published by LZI

24th Annual European Symposium on Algorithms (ESA 2016)