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
