Portal - ESA 2018

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

Bergamini, Elisabetta

Boissonnat, Jean-Daniel

Carstens, Corrie Jacobien

Chakraborty, Diptarka

Chakraborty, Sankardeep

da Fonseca, Guilherme D.

Feldmann, Andreas Emil

Italiano, Giuseppe F.

Jiang, Shaofeng H.-C.

Komusiewicz, Christian

Korenwein, Viatcheslav

Lolakapuri, Phani Raj

Raymond, Jean-Florent

van der Grinten, Alexander

van Leeuwen, Erik Jan

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

26th Annual European Symposium on Algorithms (ESA 2018)