ESA 2015
14 -16 September, Patras, Greece

ESA 2015 Accepted Papers

  • Moran Feldman.
    Maximizing Symmetric Submodular Functions
  • Marc Bury and Chris Schwiegelshohn.
    Sublinear Estimation of Weighted Matchings in Dynamic Data Streams
  • Bart M. P. Jansen and Stefan Kratsch.
    A structural approach to kernels for ILPs: Treewidth and Total Unimodularity
  • Michael Etscheid and Heiko Röglin.
    Smoothed Analysis of the Squared Euclidean Maximum-Cut Problem
  • Gill Barequet, Günter Rote and Mira Shalah.
    $\lambda > 4$
  • Ashish Chiplunkar, Sumedh Tirodkar and Sundar Vishwanathan.
    On Randomized Algorithms for Matching in the Online Preemptive Model
  • Jara Uitto and Roger Wattenhofer.
    Ignorant vs. Anonymous Recommendations
  • Rasmus Pagh, Ninh Pham, Francesco Silvestri and Morten Stockel.
    I/O-Efficient Similarity Join
  • Meirav Zehavi.
    Mixing Color Coding-Related Techniques (Student Paper)

  • Niklas Baumstark, Guy Blelloch and Julian Shun.
    Efficient Implementation of a Synchronous Parallel Push-Relabel Algorithm
  • Arijit Ghosh, Jean-Daniel Boissonnat and Ramsay Dyer.
    A probabilistic approach to reducing algebraic complexity of Delaunay triangulations
  • Kyle Genova and David Williamson.
    An Experimental Evaluation of the Best-of-Many Christofides' Algorithm for the Traveling Salesman Problem
  • Hossein Esfandiari, Mohammadtaghi Hajiaghayi, Vahid Liaghat and Morteza Monemizadeh.
    Prophet Secretary
  • Sreyash Kenkre, Vinayaka Pandit, Manish Purohit and Rishi Saket.
    On the Approximability of Digraph Ordering
  • Pål Grønås Drange and Michał Pilipczuk.
    A polynomial kernel for Trivially Perfect Editing
  • Dániel Marx and Michał Pilipczuk.
    Optimal parameterized algorithms for planar facility location problems using Voronoi diagrams
  • Éric Colin de Verdière.
    Multicuts in Planar and Bounded-Genus Graphs with Bounded Number of Terminals
  • Torsten Mütze and Jerri Nummenpalo.
    Efficient computation of middle levels Gray codes
  • Anna Großwendt and Heiko Röglin.
    Improved Analysis of Complete-Linkage Clustering
  • Hans L. Bodlaender and Jesper Nederlof.
    Subexponential time algorithms for finding small tree and path decompositions
  • Marek Adamczyk, Fabrizio Grandoni and Joydeep Mukherjee.
    Improved Approximation Algorithms for Stochastic Matching
  • Hadas Shachnai and Meirav Zehavi.
    A Multivariate Framework for Weighted FPT Algorithms
  • Kevin Buchin , Tim Ophelders and Bettina Speckmann.
    Computing the Similarity Between Moving Curves
  • Mohammadtaghi Hajiaghayi, Guy Kortsarz, Robert MacDavid, Manish Purohit and Kanthi Sarpatwar.
    Approximation Algorithms for Connected Maximum Cut and Related Problems
  • Iffat Chowdhury and Matt Gibson.
    A Characterization of Consistent Digital Line Segments in Two Dimensions
  • Michael Dinitz, Michael Schapira and Asaf Valadarsky.
    Explicit Expanding Expanders
  • Yuval Emek, Tobias Langner and Roger Wattenhofer.
    The Price of Matching with Metric Preferences
  • Gregory Gutin, Mark Jones and Magnus Wahlström.
    Structural Parameterizations of the Mixed Chinese Postman Problem
  • Micha Sharir, Adam Sheffer and Noam Solomon.
    Incidences with curves in $\mathbb{R}^d$
  • Paul Duetting and Robert Kleinberg.
    Polymatroid Prophet Inequalities
  • Dan Halperin, Michael Kerber and Doron Shaharabani.
    The Offset Filtration of Convex Objects
  • Daniel Graf.
    How to Sort by Walking on a Tree
  • Christian Konrad.
    Maximum Matching in Turnstile Streams
  • Kenta Kitsunai, Yasuaki Kobayashi and Hisao Tamaki.
    On the Pathwidth of Almost Semicomplete Digraphs
  • Yossi Azar and Oren Gilon.
    Buffer Management for Packets with Processing Times
  • Elisabetta Bergamini and Henning Meyerhenke.
    Fully-dynamic Approximation of Betweenness Centrality
  • Davaatseren Baatar, Mohan Krishnamoorthy and Andreas Ernst.
    A triplet-based branch-and-bound algorithm for the shift mininisation personnel task scheduling problem
  • Ilia Gorelik, Amos Fiat, Haim Kaplan and Slava Novgorodov.
    The Temp Secretary Problem
  • Spyros Sioutas, Efrosini Sourla, Kostas Tsichlas and Christos Zaroliagis.
    D3-Tree: A Dynamic Deterministic Decentralized Structure
  • Nicolas Bonichon, Prosenjit Bose, Jean-Lou De Carufel, Ljubomir Perkovic and André van Renssen.
    Upper and Lower Bounds for Online Routing on Delaunay Triangulations
  • Djamal Belazzougui, Patrick Hagge Cording, Simon J. Puglisi and Yasuo Tabei.
    Access, rank, and select in grammar-compressed strings
  • Xin He and Dayu He.
    Monotone Drawings of 3-Connected Plane Graphs
  • Yoichi Iwata and Yuichi Yoshida.
    On the Equivalence among Problems of Bounded Width
  • Sascha Witt.
    Trip-Based Public Transit Routing
  • Jacob Holm, Eva Rotenberg and Christian Wulff-Nilsen.
    Faster Fully-Dynamic Minimum Spanning Forest
  • Spyros Angelopoulos, Giorgio Lucarelli and Kim Thang Nguyen.
    Primal-dual and dual-fitting analysis of online scheduling algorithms for generalized flow time problems
  • Alon Baram, Efi Fogel, Dan Halperin, Michael Hemmer and Sebastian Morr.
    Exact Minkowski Sums of Polygons With Holes
  • Adam Kurpisz, Monaldo Mastrolilli and Samuli Leppänen.
    A Lasserre Lower Bound for the Min-Sum Single Machine Scheduling Problem
  • Sariel Har-Peled and Kent Quanrud.
    Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs
  • Oliver Göbel, Thomas Kesselheim and Andreas Tönnis.
    Online Appointment Scheduling in the Random Order Model
  • Ulrik Brandes, Michael Hamann, Ben Strasser and Dorothea Wagner.
    Fast Quasi-Threshold Editing
  • Arnaud De Mesmay and Vincent Viallat Cohen Addad.
    A Fixed Parameter Tractable Approximation Scheme for the Optimal Cut Graph of a Surface
  • Mohammadhossein Bateni, Sina Dehghani, Mohammadtaghi Hajiaghayi and Saeed Seddighin.
    Revenue Maximization for Selling Multiple Correlated Items
  • Ariel Gabizon, Daniel Lokshtanov and Michał Pilipczuk.
    Fast Algorithms for Parameterized Problems with Relaxed Disjointness Constraints
  • George Christodoulou, Alkmini Sgouritsa and Bo Tang.
    On the Efficiency of All-Pay Mechanisms
  • Michael Bekos, Till Bruckdorfer, Michael Kaufmann and Chrysanthi Raftopoulou.
    1-Planar Graphs have Constant Book Thickness
  • Davide Bilò, Fabrizio Grandoni, Luciano Gualà, Stefano Leucci and Guido Proietti.
    Improved Purely Additive Fault-Tolerant Spanners
  • Michele Borassi, David Coudert, Pierluigi Crescenzi and Andrea Marino.
    On Computing the Hyperbolicity of Real-World Graphs
  • Loukas Georgiadis, Giuseppe F. Italiano, Charis Papadopoulos and Nikos Parotsidis.
    Approximating the Smallest Spanning Subgraph for 2-Edge-Connectivity in Directed Graphs
  • Johannes Fischer, Travis Gagie, Pawel Gawrychowski and Tomasz Kociumaka.
    Approximating LZ77 via Small-Space Multiple-Pattern Matching
  • Jie Gao and Mayank Goswami.
    Medial Axis Based Routing Has Constant Load Balancing Factor
  • Abbas Bazzi and Ashkan Norouzi-Fard.
    Towards Tight Lower Bounds for Scheduling Problems
  • Jaroslaw Byrka, Thomas Pensyl, Bartosz Rybicki, Joachim Spoerhase, Aravind Srinivasan and Khoa Trinh.
    An Improved Approximation Algorithm for Knapsack Median Using Sparsification
  • Chandra Chekuri, Thapanapong Rukkanchanunt and Chao Xu.
    On Element-Connectivity Preserving Graph Simplification
  • Adam Bohn, Yuri Faenza, Samuel Fiorini, Vissarion Fisikopoulos, Marco Macchia and Kanstantsin Pashkovich.
    Enumeration of 2-level polytopes
  • Parinya Chalermsook, Mayank Goswami, Laszlo Kozma, Kurt Mehlhorn and Thatchaphol Saranurak.
    Self-Adjusting Binary Search Trees: What Makes Them Tick?
  • Christina Boucher, Christine Lo and Daniel Lokshtanov.
    Consensus Patterns (Probably) Has no EPTAS
  • Leah Epstein and Elena Kleiman.
    Selfish vector packing
  • Andrew Goldberg, Sagi Hed, Haim Kaplan, Pushmeet Kohli, Robert Tarjan and Renato Werneck.
    Faster and More Dynamic Maximum Flow by Incremental Breadth-First Search
  • Mathias Bæk Tejs Knudsen and Morten Stöckel.
    Quicksort, Largest Bucket, and Min-Wise Hashing with Limited Independence
  • Nabil Mustafa, Saurabh Ray and Norbert Bus.
    Geometric Hitting Sets for Disks: Theory and Practice
  • Friedrich Eisenbrand, Shay Moran, Rom Pinchasi and Martin Skutella.
    Node-balancing by edge-increments
  • Glencora Borradaile, Amir Nayyeri and Farzad Zafarani.
    Towards shortest vertex-disjoint paths in undirected planar graphs
  • Ian Munro and Yakov Nekrich.
    Compressed Data Structures for Dynamic Sequences
  • Riko Jacob and Morten Stöckel.
    Fast Output-Sensitive Matrix Multiplication
  • Fritz Bökler and Petra Mutzel.
    Output-Sensitive Algorithms for Enumerating the Extreme Nondominated Points of Multiobjective Combinatorial Optimization Problems
  • Nicole Megow, Julie Meißner and Martin Skutella.
    Randomization Helps Computing a Minimum Spanning Tree under Uncertainty
  • Hossein Esfandiari, Mohammadtaghi Hajiaghayi, Jochen Konemann, Hamid Mahini, David Malec and Laura Sanita.
    Approximate Deadline-Scheduling with Precedence Constraints
  • Peyman Afshani and Nodari Sitchinava.
    Sorting and Permuting without Bank Conflicts on GPUs
  • Matt Gibson, Erik Krohn and Qing Wang.
    A Characterization of Visibility Graphs for Pseudo-Polygons
  • Pål Grønås Drange, Markus Sortland Dregi, Daniel Lokshtanov and Blair D. Sullivan.
    On the Threshold of Intractability
  • Anthony Kim.
    Welfare Maximization with Deferred Acceptance Auctions in Reallocation Problems
  • Colin White.
    Lower Bounds in the Preprocessing and Query Phases of Routing Algorithms
  • George Rabanca, Amotz Bar-Noy, David Peleg and Ivo Vigan.
    Improved Approximation Algorithms for Weighted 2-path Partitions
  • Helmut Alt, Mark de Berg and Christian Knauer.
    Approximating Minimum-Area Rectangular and Convex Containers for Packing Convex Polygons
  • Raphael Clifford, Allyx Fontaine, Ely Porat, Benjamin Sach and Tatiana Starikovskaya.
    Dictionary matching in a stream