ESA 2014 Accepted Papers
Design and Analysis (Track A)
- Gregory Gutin, Mark Jones and Bin Sheng
Parameterized Complexity of the k-Arc Chinese Postman Problem
- Moshe Lewenstein, Ian Munro, Patrick K. Nicholson and Venkatesh Raman
Improved Explicit Data Structures in the Bitprobe Model
- Rasmus Pagh and Morten Stöckel
The Input/Output Complexity of Sparse Matrix Multiplication
- Zhewei Wei and Ke Yi
Equivalence between Priority Queues and Sorting in External Memory
- Dominique Attali, Olivier Devillers, Marc Glisse and Sylvain Lazard
Recognizing shrinkable complexes is NP-complete
- Stacey Jeffery, Frederic Magniez and Ronald de Wolf
Optimal parallel quantum query algorithms
- Jianer Chen, Wenjun Li and Jianxin Wang
Deeper Local Search for better Approximation on Maximum Internal Spanning Trees
- Sariel Har-Peled and Subhro Roy
Approximating the Maximum Overlap of Polygons under Translation
- Bart M. P. Jansen
Turing Kernelization for Finding Long Paths and Cycles in Restricted Graph Classes
- Martin Grohe, Kristian Kersting, Martin Mladenov and Aziz Erkal Selman
Dimension Reduction via Colour Refinement
- Ivan Bliznets, Fedor Fomin, Marcin Pilipczuk and Michał Pilipczuk
A subexponential parameterized algorithm for Proper Interval Completion
- Jingcheng Liu, Pinyan Lu and Chihao Zhang
FPTAS of Counting Weighted Edge Covers
- Guy Even, Moti Medina and Dana Ron
Deterministic Stateless Local Centralized Algorithms for Bounded Degree Graphs
- Fidaa Abed, Jose Correa and Chien-Chung Huang
Optimal Coordination Mechanisms for Multi-Job Scheduling Games
- Bryan T. Wilkinson
Amortized Bounds for Dynamic Orthogonal Range Searching
- Andrew McGregor, Eric Price and Sofya Vorotnikova
Trace Reconstruction Revisited
- Pavol Hell, Bojan Mohar and Arash Rafiey
Ordering without forbidden patterns
- Matt Gibson, Kasturi Varadarajan and Xiaodong Wu
Computing Regions Decomposable into m Stars
- Karl Bringmann, Tobias Friedrich and Anton Krohmer
De-anonymization of Heterogeneous Random Graphs in Quasilinear Time
- Moses Charikar, Monika Henzinger and Huy Nguyen
Online Bipartite Matching with Decomposable Weights
- Alina Ene and Huy Nguyen
From Graph to Hypergraph Multiway Partition: Is the Single Threshold the Only Route?
- Zdenek Dvorak and Matthias Mnich
Large Independent Sets in Triangle-Free Planar Graphs
- Joshua Wang
Space-Efficient Randomized Algorithms for K-SUM
- Pooya Davoodi, Jeremy Fineman, John Iacono and Ozgur Ozkan
Cache-Oblivious Persistence
- Zdenek Dvorak, Martin Kupec and Vojtech Tuma
A dynamic data structure for MSO properties in graphs with bounded tree-depth
- Thomas Bläsius, Ignaz Rutter and Guido Brückner
Complexity of Higher-Degree Orthogonal Graph Embedding in the Kandinsky Model
- Venkatesan Chakaravarthy, Anamitra Roy Choudhury, Shalmoli Gupta, Sambuddha Roy and Yogish Sabharwal
Improved Algorithms for Resource Allocation Under Varying Capacity
- Michael Hoffmann, Vincent Kusters and Tillmann Miltzow
Halving Balls in Deterministic Linear Time
- Romeo Rizzi and Alexandru I. Tomescu
Faster FPTASes for counting and random generation of Knapsack solutions
- Tomasz Kociumaka, Tatiana Starikovskaya and Hjalte Wedel Vildhøj
Sublinear Space Algorithms for the Longest Common Substring Problem
- Petr Golovach, Marcin Kamiński, Spyridon Maniatis and Dimitrios Thilikos
The Parameterized Complexity of Graph Cyclability
- Michael Bekos, Thomas C. Van Dijk, Martin Fink, Philipp Kindermann, Stephen Kobourov, Sergey Pupyrev, Joachim Spoerhase and Alexander Wolff
Improved Approximation Algorithms for Box Contact Representations
- Niv Buchbinder, Shahar Chen and Seffi Naor
Competitive Algorithms for Restricted Caching and Matroid Caching
- Rui Ferreira, Roberto Grossi, Romeo Rizzi, Gustavo Sacomoto and Marie-France Sagot
Amortized Õ(|V|)-Delay Algorithm for Listing Chordless Cycles in Undirected Graphs
- Daniel Larkin and Robert Tarjan
Nested Set Union
- Hadas Shachnai and Meirav Zehavi
Representative Families: A Unified Tradeoff-Based Approach
- Alantha Newman
The traveling salesman problem on subquartic graphs
- Flavio K. Miyazawa, Lehilton L. C. Pedrosa, Rafael C. S. Schouery, Maxim Sviridenko and Yoshiko Wakabayashi
Polynomial-Time Approximation Schemes for Circle Packing Problems
- Harald Räcke and Chintan Shah
Improved Guarantees for Tree Cut Sparsifiers
- Samuel Fiorini, R. Krithika, N.S. Narayanaswamy and Venkatesh Raman
LP Approaches to Improved Approximation for Clique Transversal in Perfect Graphs
- Fedor Fomin, Daniel Lokshtanov, Fahad Panolan and Saket Saurabh
Representative Sets of Product Families
- Rafel Jaume, Matthias Henze, Micha Sharir, Rinat Ben-Avraham, Orit E. Raz, Balazs Keszegh and Igor Tubis
Minimum Partial Matching and Hausdorff RMS-Distance Under Translation: Combinatorics and Algorithms
- Davide Bilò, Luciano Gualà, Stefano Leucci and Guido Proietti
Fault-Tolerant Approximate Shortest-Path Trees
- Caleb Malchik and Andrew Winslow
Tight Bounds for Active Self-Assembly Using an Insertion Primitive
- Pawel Gawrychowski, Moshe Lewenstein and Patrick K. Nicholson
Weighted ancestors in suffix trees
- Omar Darwish and Amr Elmasry
Optimal Time-Space Tradeoff for the 2D Convex-Hull Problem
- Daniel Lokshtanov, Saket Saurabh and Ondrej Suchy
Solving Multicut Faster than 2^n
- Timothy M. Chan, Meng He, J. Ian Munro and Gelin Zhou
Succinct Indices for Path Minimum, with Applications to Path Reporting
- Anupam Gupta and Marco Molinaro
How Experts Can Solve LPs Online
- Siu-Wing Cheng, Liam Mencel and Antoine Vigneron
A Faster Algorithm for Computing Straight Skeletons
- Parinya Chalermsook, Sandy Heydrich, Eugenia Holm and Andreas Karrenbauer
Nearly Tight Approximability Results for Minimum Biclique Cover and Partition
- Charilaos Efthymiou
Switching colouring of G(n,d/n) for sampling up to Gibbs Uniqueness Threshold
- Pankaj K. Agarwal, Sariel Har-Peled, Subhash Suri, Hakan Yıldız and Wuzhou Zhang
Convex Hulls under Uncertainty
- Amir Abboud, Kevin Lewi and Ryan Williams
Losing Weight by Gaining Edges
- Arnab Bhattacharyya
Polynomial decompositions in polynomial time
- Michael A. Bender, Martin Farach-Colton, Mayank Goswami, Dzejla Medjedovic, Pablo Montes and Meng-Tsung Tsai
The Batched Predecessor Problem in External Memory
- Rachit Agarwal
The Space-Stretch-Time Tradeoff in Distance Oracles
Engineering and Applications (Track B)
