ESA 2017 September 4-6, 2017 - Vienna, Austria

25th Annual European Symposium on Algorithms (ESA 2017)



Kirk Pruhs and Christian Sohler (Eds.)
ISBN 978-3-95977-049-1, LIPICS Vol. 87 ISSN 1868-8969
Additional Information
License
Conference Website
Complete volume (PDF, 35 MB)
Search Publication Server

Authors
  • Afshani, Peyman
  • Agarwal, Pankaj K.
  • Aiger, Dror
  • Aissi, Hassene
  • Albers, Susanne
  • Antunes, Daniel
  • Axtmann, Michael
  • Balogh, Janos
  • Baum, Moritz
  • Becker, Amariah
  • Bekesi, Jozsef
  • Berczi, Kristof
  • Bessy, Stéphane
  • Bhattacharya, Sayan
  • Bille, Philip
  • Bilò, Vittorio
  • Bonamy, Marthe
  • Bosman, Thomas
  • Bougeret, Marin
  • Bringmann, Karl
  • Buchbinder, Niv
  • Burton, Benjamin
  • Chambers, Erin
  • Chan, T.-H. Hubert
  • Chan, Timothy M.
  • Chatziafratis, Vaggos
  • Chini, Peter
  • Choudhary, Aruni
  • Christiansen, Anders Roy
  • Cormode, Graham
  • Cygan, Marek
  • Daskalakis, Constantinos
  • Das, Syamantak
  • Devanny, William E.
  • Dey, Tamal K.
  • Dibbelt, Julian
  • Dosa, Gyorgy
  • Eden, Alon
  • Edwards, Katherine
  • Epstein, Leah
  • Ettienne, Mikko Berggren
  • Ezra, Tomer
  • Feldman, Michal
  • Ferber, Aaron
  • Ferizovic, Daniel
  • Fineman, Jeremy T.
  • Freund, Daniel
  • Friedrich, Tobias
  • Gagie, Travis
  • Gajjar, Kshitij
  • Gawrychowski, Pawel
  • Golan, Shay
  • Gold, Omer
  • Gollapudi, Sreenivas
  • Goodrich, Michael T.
  • Goranci, Gramoz
  • Gørtz, Inge Li
  • Gupta, Manoj
  • Guruganesh, Guru
  • Gutin, Gregory
  • Hassidim, Avinatan
  • Henzinger, Monika
  • Hershberger, John
  • Holm, Jacob
  • Iglesias, Jennifer
  • Im, Sungjin
  • Italiano, Giuseppe F.
  • I, Tomohiro
  • Jiang, Shaofeng H.-C.
  • Jowhari, Hossein
  • Kaplan, Haim
  • Karczmarz, Adam
  • Kawase, Yasushi
  • Kempa, Dominik
  • Kerber, Michael
  • Keusch, Ralph
  • Klein, Philip N.
  • Knop, Dusan
  • Kobayashi, Yusuke
  • Kolberg, Jonathan
  • Kollias, Kostas
  • Kopelowitz, Tsvi
  • Kosolobov, Dmitry
  • Koutecky, Martin
  • Kowalik, Lukasz
  • Krasnopolsky, Nadav
  • Krebs, Andreas
  • Krohmer, Anton
  • Kumar, Neeraj
  • Kutiel, Gilad
  • Lacki, Jakub
  • Lengler, Johannes
  • Leniowski, Dariusz
  • Levin, Asaf
  • Liskiewicz, Maciej
  • Li, Zhijiang
  • Lokshtanov, Daniel
  • Mahjoub, Ali Ridha
  • Maier, Tobias
  • Mampentzidis, Konstantinos
  • Manzini, Giovanni
  • Marx, Dániel
  • Mathieu, Claire
  • Meulemans, Wouter
  • Meyerhenke, Henning
  • Meyer, Roland
  • Mnich, Matthias
  • Mohan, Divyarthi
  • Monemizadeh, Morteza
  • Moseley, Benjamin
  • Mozes, Shay
  • Mustafa, Nabil H.
  • Muthukrishnan, S.
  • Muzi, Irene
  • Neuen, Daniel
  • Nutov, Zeev
  • Olver, Neil
  • Ophelders, Tim
  • Panigrahi, Debmalya
  • Paul, Alice
  • Peng, Pan
  • Pilipczuk, Marcin
  • Pilipczuk, Michal
  • Pliatsika, Venetia
  • Porat, Ely
  • Pruhs, Kirk
  • Radhakrishnan, Jaikumar
  • Raghvendra, Sharath
  • Ramanujan, M. S.
  • Ravi, R.
  • Rawitz, Dror
  • Reidl, Felix
  • Rossi, Alfred
  • Rotenberg, Eva
  • Rothenberger, Ralf
  • Roth, Marc
  • Rottenstreich, Ori
  • Roughgarden, Tim
  • Roy, Sasanka
  • Rubin, Natan
  • Saivasan, Prakash
  • Sakamoto, Hiroshi
  • Sanders, Peter
  • Sanita, Laura
  • Sankowski, Piotr
  • Sauerwald, Thomas
  • Saulpic, David
  • Saurabh, Saket
  • Schibler, Thomas
  • Schraink, Sebastian
  • Schug, Alexander
  • Schuster, Martin R.
  • Schweitzer, Pascal
  • Segev, Danny
  • Sharir, Micha
  • Shmoys, David B.
  • Sidiropoulos, Anastasios
  • Skrepetos, Dimitrios
  • Socala, Arkadiusz
  • Sohler, Christian
  • Speckmann, Bettina
  • Stein, Clifford
  • Stølting Brodal, Gerth
  • Suri, Subhash
  • Sutton, Andrew M.
  • Takabatake, Yoshimasa
  • Tamaki, Hisao
  • Tang, Zhihao Gavin
  • Taubert, Oskar
  • Thiebaut, Jocelyn
  • Thomas, Antonis
  • Tkach, Yevgeny
  • van Duijn, Ingo
  • van Kreveld, Marc
  • Venturini, Rossano
  • Vinci, Cosimo
  • Vondrak, Jan
  • Wagner, Dorothea
  • Wahlström, Magnus
  • Wegner, Michael
  • Weimann, Oren
  • Wei, Zhewei
  • Wiese, Andreas
  • Williamson, David P.
  • Witt, Sascha
  • Wollan, Paul
  • Woodruff, David P.
  • Wrochna, Marcin
  • Wu, Xiaowei
  • Zeh, Norbert
  • Zündorf, Tobias
    		•

    		  
    Front Matter, Table of Contents, Preface, Programm Commitees, External Reviewers
    Authors: Pruhs, Kirk ; Sohler, Christian

    Abstract | Document (372 KB) | BibTeX

    Sketching for Geometric Problems (Invited Talk)
    Authors: Woodruff, David P.

    Abstract | Document (311 KB) | BibTeX

    Permuting and Batched Geometric Lower Bounds in the I/O Model
    Authors: Afshani, Peyman ; van Duijn, Ingo

    Abstract | Document (539 KB) | BibTeX

    Independent Range Sampling, Revisited
    Authors: Afshani, Peyman ; Wei, Zhewei

    Abstract | Document (654 KB) | BibTeX

    Approximate Nearest Neighbor Search Amid Higher-Dimensional Flats
    Authors: Agarwal, Pankaj K. ; Rubin, Natan ; Sharir, Micha

    Abstract | Document (558 KB) | BibTeX

    Output Sensitive Algorithms for Approximate Incidences and Their Applications
    Authors: Aiger, Dror ; Kaplan, Haim ; Sharir, Micha

    Abstract | Document (576 KB) | BibTeX

    Randomized Contractions for Multiobjective Minimum Cuts
    Authors: Aissi, Hassene ; Mahjoub, Ali Ridha ; Ravi, R.

    Abstract | Document (451 KB) | BibTeX

    Tight Bounds for Online Coloring of Basic Graph Classes
    Authors: Albers, Susanne ; Schraink, Sebastian

    Abstract | Document (528 KB) | BibTeX

    Combinatorics of Local Search: An Optimal 4-Local Hall's Theorem for Planar Graphs
    Authors: Antunes, Daniel ; Mathieu, Claire ; Mustafa, Nabil H.

    Abstract | Document (804 KB) | BibTeX

    In-Place Parallel Super Scalar Samplesort (IPSSSSo)
    Authors: Axtmann, Michael ; Witt, Sascha ; Ferizovic, Daniel ; Sanders, Peter

    Abstract | Document (935 KB) | BibTeX

    Online Bin Packing with Cardinality Constraints Resolved
    Authors: Balogh, Janos ; Bekesi, Jozsef ; Dosa, Gyorgy ; Epstein, Leah ; Levin, Asaf

    Abstract | Document (441 KB) | BibTeX

    Modeling and Engineering Constrained Shortest Path Algorithms for Battery Electric Vehicles
    Authors: Baum, Moritz ; Dibbelt, Julian ; Wagner, Dorothea ; Zündorf, Tobias

    Abstract | Document (556 KB) | BibTeX

    A Quasi-Polynomial-Time Approximation Scheme for Vehicle Routing on Planar and Bounded-Genus Graphs
    Authors: Becker, Amariah ; Klein, Philip N. ; Saulpic, David

    Abstract | Document (755 KB) | BibTeX

    The Directed Disjoint Shortest Paths Problem
    Authors: Berczi, Kristof ; Kobayashi, Yusuke

    Abstract | Document (507 KB) | BibTeX

    Triangle Packing in (Sparse) Tournaments: Approximation and Kernelization
    Authors: Bessy, Stéphane ; Bougeret, Marin ; Thiebaut, Jocelyn

    Abstract | Document (681 KB) | BibTeX

    Improved Algorithm for Dynamic b-Matching
    Authors: Bhattacharya, Sayan ; Gupta, Manoj ; Mohan, Divyarthi

    Abstract | Document (465 KB) | BibTeX

    Fast Dynamic Arrays
    Authors: Bille, Philip ; Christiansen, Anders Roy ; Ettienne, Mikko Berggren ; Gørtz, Inge Li

    Abstract | Document (637 KB) | BibTeX

    On the Impact of Singleton Strategies in Congestion Games
    Authors: Bilò, Vittorio ; Vinci, Cosimo

    Abstract | Document (548 KB) | BibTeX

    Tight Lower Bounds for the Complexity of Multicoloring
    Authors: Bonamy, Marthe ; Kowalik, Lukasz ; Pilipczuk, Michal ; Socala, Arkadiusz ; Wrochna, Marcin

    Abstract | Document (633 KB) | BibTeX

    Exploring the Tractability of the Capped Hose Model
    Authors: Bosman, Thomas ; Olver, Neil

    Abstract | Document (599 KB) | BibTeX

    Sampling Geometric Inhomogeneous Random Graphs in Linear Time
    Authors: Bringmann, Karl ; Keusch, Ralph ; Lengler, Johannes

    Abstract | Document (562 KB) | BibTeX

    Cache Oblivious Algorithms for Computing the Triplet Distance Between Trees
    Authors: Stølting Brodal, Gerth ; Mampentzidis, Konstantinos

    Abstract | Document (675 KB) | BibTeX

    Online Algorithms for Maximum Cardinality Matching with Edge Arrivals
    Authors: Buchbinder, Niv ; Segev, Danny ; Tkach, Yevgeny

    Abstract | Document (484 KB) | BibTeX

    Computing Optimal Homotopies over a Spiked Plane with Polygonal Boundary
    Authors: Burton, Benjamin ; Chambers, Erin ; van Kreveld, Marc ; Meulemans, Wouter ; Ophelders, Tim ; Speckmann, Bettina

    Abstract | Document (794 KB) | BibTeX

    Online Submodular Maximization Problem with Vector Packing Constraint
    Authors: Chan, T.-H. Hubert ; Jiang, Shaofeng H.-C. ; Tang, Zhihao Gavin ; Wu, Xiaowei

    Abstract | Document (598 KB) | BibTeX

    Faster Approximate Diameter and Distance Oracles in Planar Graphs
    Authors: Chan, Timothy M. ; Skrepetos, Dimitrios

    Abstract | Document (432 KB) | BibTeX

    Stability and Recovery for Independence Systems
    Authors: Chatziafratis, Vaggos ; Roughgarden, Tim ; Vondrak, Jan

    Abstract | Document (649 KB) | BibTeX

    On the Complexity of Bounded Context Switching
    Authors: Chini, Peter ; Kolberg, Jonathan ; Krebs, Andreas ; Meyer, Roland ; Saivasan, Prakash

    Abstract | Document (597 KB) | BibTeX

    Improved Approximate Rips Filtrations with Shifted Integer Lattices
    Authors: Choudhary, Aruni ; Kerber, Michael ; Raghvendra, Sharath

    Abstract | Document (860 KB) | BibTeX

    The Sparse Awakens: Streaming Algorithms for Matching Size Estimation in Sparse Graphs
    Authors: Cormode, Graham ; Jowhari, Hossein ; Monemizadeh, Morteza ; Muthukrishnan, S.

    Abstract | Document (544 KB) | BibTeX

    Improving TSP Tours Using Dynamic Programming over Tree Decompositions
    Authors: Cygan, Marek ; Kowalik, Lukasz ; Socala, Arkadiusz

    Abstract | Document (611 KB) | BibTeX

    On Minimizing the Makespan When Some Jobs Cannot Be Assigned on the Same Machine
    Authors: Das, Syamantak ; Wiese, Andreas

    Abstract | Document (614 KB) | BibTeX

    Optimal Stopping Rules for Sequential Hypothesis Testing
    Authors: Daskalakis, Constantinos ; Kawase, Yasushi

    Abstract | Document (556 KB) | BibTeX

    The Online House Numbering Problem: Min-Max Online List Labeling
    Authors: Devanny, William E. ; Fineman, Jeremy T. ; Goodrich, Michael T. ; Kopelowitz, Tsvi

    Abstract | Document (587 KB) | BibTeX

    Temporal Clustering
    Authors: Dey, Tamal K. ; Rossi, Alfred ; Sidiropoulos, Anastasios

    Abstract | Document (724 KB) | BibTeX

    Pricing Social Goods
    Authors: Eden, Alon ; Ezra, Tomer ; Feldman, Michal

    Abstract | Document (583 KB) | BibTeX

    Half-Integral Linkages in Highly Connected Directed Graphs
    Authors: Edwards, Katherine ; Muzi, Irene ; Wollan, Paul

    Abstract | Document (539 KB) | BibTeX

    Bounds on the Satisfiability Threshold for Power Law Distributed Random SAT
    Authors: Friedrich, Tobias ; Krohmer, Anton ; Rothenberger, Ralf ; Sauerwald, Thomas ; Sutton, Andrew M.

    Abstract | Document (632 KB) | BibTeX

    An Encoding for Order-Preserving Matching
    Authors: Gagie, Travis ; Manzini, Giovanni ; Venturini, Rossano

    Abstract | Document (466 KB) | BibTeX

    Distance-Preserving Subgraphs of Interval Graphs
    Authors: Gajjar, Kshitij ; Radhakrishnan, Jaikumar

    Abstract | Document (521 KB) | BibTeX

    Dispersion on Trees
    Authors: Gawrychowski, Pawel ; Krasnopolsky, Nadav ; Mozes, Shay ; Weimann, Oren

    Abstract | Document (477 KB) | BibTeX

    Real-Time Streaming Multi-Pattern Search for Constant Alphabet
    Authors: Golan, Shay ; Porat, Ely

    Abstract | Document (560 KB) | BibTeX

    Improved Bounds for 3SUM, k-SUM, and Linear Degeneracy
    Authors: Gold, Omer ; Sharir, Micha

    Abstract | Document (576 KB) | BibTeX

    Profit Sharing and Efficiency in Utility Games
    Authors: Gollapudi, Sreenivas ; Kollias, Kostas ; Panigrahi, Debmalya ; Pliatsika, Venetia

    Abstract | Document (479 KB) | BibTeX

    Improved Guarantees for Vertex Sparsification in Planar Graphs
    Authors: Goranci, Gramoz ; Henzinger, Monika ; Peng, Pan

    Abstract | Document (579 KB) | BibTeX

    The Power of Vertex Sparsifiers in Dynamic Graph Algorithms
    Authors: Goranci, Gramoz ; Henzinger, Monika ; Peng, Pan

    Abstract | Document (508 KB) | BibTeX

    Single-Sink Fractionally Subadditive Network Design
    Authors: Guruganesh, Guru ; Iglesias, Jennifer ; Ravi, R. ; Sanita, Laura

    Abstract | Document (530 KB) | BibTeX

    Path-Contractions, Edge Deletions and Connectivity Preservation
    Authors: Gutin, Gregory ; Ramanujan, M. S. ; Reidl, Felix ; Wahlström, Magnus

    Abstract | Document (653 KB) | BibTeX

    Dynamic Clustering to Minimize the Sum of Radii
    Authors: Henzinger, Monika ; Leniowski, Dariusz ; Mathieu, Claire

    Abstract | Document (448 KB) | BibTeX

    Shortest Paths in the Plane with Obstacle Violations
    Authors: Hershberger, John ; Kumar, Neeraj ; Suri, Subhash

    Abstract | Document (499 KB) | BibTeX

    Contracting a Planar Graph Efficiently
    Authors: Holm, Jacob ; Italiano, Giuseppe F. ; Karczmarz, Adam ; Lacki, Jakub ; Rotenberg, Eva ; Sankowski, Piotr

    Abstract | Document (605 KB) | BibTeX

    Minimizing Maximum Flow Time on Related Machines via Dynamic Posted Pricing
    Authors: Im, Sungjin ; Moseley, Benjamin ; Pruhs, Kirk ; Stein, Clifford

    Abstract | Document (418 KB) | BibTeX

    Finding Axis-Parallel Rectangles of Fixed Perimeter or Area Containing the Largest Number of Points
    Authors: Kaplan, Haim ; Roy, Sasanka ; Sharir, Micha

    Abstract | Document (508 KB) | BibTeX

    LZ-End Parsing in Linear Time
    Authors: Kempa, Dominik ; Kosolobov, Dmitry

    Abstract | Document (519 KB) | BibTeX

    Combinatorial n-fold Integer Programming and Applications
    Authors: Knop, Dusan ; Koutecky, Martin ; Mnich, Matthias

    Abstract | Document (715 KB) | BibTeX

    Local Search Algorithms for Maximum Carpool Matching
    Authors: Kutiel, Gilad ; Rawitz, Dror

    Abstract | Document (585 KB) | BibTeX

    Computing Maximum Agreement Forests without Cluster Partitioning is Folly
    Authors: Li, Zhijiang ; Zeh, Norbert

    Abstract | Document (690 KB) | BibTeX

    A Linear-Time Parameterized Algorithm for Node Unique Label Cover
    Authors: Lokshtanov, Daniel ; Ramanujan, M. S. ; Saurabh, Saket

    Abstract | Document (561 KB) | BibTeX

    Dynamic Space Efficient Hashing
    Authors: Maier, Tobias ; Sanders, Peter

    Abstract | Document (1,059 KB) | BibTeX

    Subexponential Parameterized Algorithms for Graphs of Polynomial Growth
    Authors: Marx, Dániel ; Pilipczuk, Marcin

    Abstract | Document (577 KB) | BibTeX

    Benchmark Graphs for Practical Graph Isomorphism
    Authors: Neuen, Daniel ; Schweitzer, Pascal

    Abstract | Document (692 KB) | BibTeX

    On the Tree Augmentation Problem
    Authors: Nutov, Zeev

    Abstract | Document (547 KB) | BibTeX

    Prize-Collecting TSP with a Budget Constraint
    Authors: Paul, Alice ; Freund, Daniel ; Ferber, Aaron ; Shmoys, David B. ; Williamson, David P.

    Abstract | Document (482 KB) | BibTeX

    Counting Restricted Homomorphisms via Möbius Inversion over Matroid Lattices
    Authors: Roth, Marc

    Abstract | Document (546 KB) | BibTeX

    Clustering in Hypergraphs to Minimize Average Edge Service Time
    Authors: Rottenstreich, Ori ; Kaplan, Haim ; Hassidim, Avinatan

    Abstract | Document (580 KB) | BibTeX

    K-Dominance in Multidimensional Data: Theory and Applications
    Authors: Schibler, Thomas ; Suri, Subhash

    Abstract | Document (471 KB) | BibTeX

    New Abilities and Limitations of Spectral Graph Bisection
    Authors: Schuster, Martin R. ; Liskiewicz, Maciej

    Abstract | Document (556 KB) | BibTeX

    A Space-Optimal Grammar Compression
    Authors: Takabatake, Yoshimasa ; I, Tomohiro ; Sakamoto, Hiroshi

    Abstract | Document (1,583 KB) | BibTeX

    Positive-Instance Driven Dynamic Programming for Treewidth
    Authors: Tamaki, Hisao

    Abstract | Document (489 KB) | BibTeX

    Exponential Lower Bounds for History-Based Simplex Pivot Rules on Abstract Cubes
    Authors: Thomas, Antonis

    Abstract | Document (669 KB) | BibTeX

    Maxent-Stress Optimization of 3D Biomolecular Models
    Authors: Wegner, Michael ; Taubert, Oskar ; Schug, Alexander ; Meyerhenke, Henning

    Abstract | Document (634 KB) | BibTeX

    		  



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