Table of Contents
Invited Talk
The Robustness of Level Sets Paul Bendich Herbert Edelsbrunner Dmitriy Morozov Amit Patel 1
Session 1a
Solving an Avionics Real-Time Scheduling Problem by Advanced IP-Methods Friedrich Eisenbrand Karthikeyan Kesavan Raju S. Mattikalli Martin Niemeier Arnold W. Nordsieck Martin Skutella José Verschae Andreas Wiese 11
Non-clairvoyant Speed Scaling for Weighted Flow Time Sze-Hang Chan Tak- Wah Lam Lap-Kei Lee 23
A Robust PTAS for Machine Covering and Packing Martin Skutella José Verschae 36
Session 1b
Balancing Degree, Diameter and Weight in Euclidean Spanners Shay Solomon Michael Elkin 48
Testing Euclidean Spanners Frank Hellweg Melanie Schmidt Christian Sohler 60
Fast Approximation in Subspaces by Doubling Metric Decomposition Marek Cygan Lukasz Kowalik Marcin Mucha Marcin Pilipczuk Piotr Sankowski 72
f-Sensitivity Distance Oracles and Routing Schemes Shiri Chechik Michael Langberg David Peleg Liam Roditty 84
Session 2a
Fast Minor Testing in Planar Graphs Isolde Adler Frederic Dorn Fedor V. Fomin Ignasi Sau Dimitrios M. Thilikos 97
On the Number of Spanning Trees a Planar Graph Can Have Kevin Buchin André Schulz 110
Contractions of Planar Graphs in Polynomial Time Marcin Kaminski Daniël Paulusma Dimitrios M. Thilikos 122
Session 2b
Communication Complexity of Quasirandom Rumor Spreading Petra Berenbrink Robert Elsässer Thomas Sauerwald 134
A Complete Characterization of Group-Strategyproof Mechanisms of Cost-Sharing Emmanouil Pountourakis Angelina Vidali 146
Contribution Games in Social Networks Elliot Anshelevich Martin Hoefer 158
Session 3a
Improved Bounds for Online Stochastic Matching Bahman Bahmani Michael Kapralov 170
Online Stochastic Packing Applied to Display Ad Allocation Jon Feldman Monika Henzinger Nitish Korula Vahab S. Mirrokni Cliff Stein 182
Caching Is Hard - Even in the Fault Model Marek Chrobak Gerhard J. Woeginger Kazuhisa Makino Haifeng Xu 195
Session 3b
Superselectors: Efficient Constructions and Applications Ferdinando Cicalese Ugo Vaccaro 207
Estimating the Average of a Lipschitz-Continuous Function from One Sample Abhimanyu Das David Kempe 219
Streaming Graph Computations with a Helpful Advisor Graham Cormode Michael Mitzenmacher Justin Thaler 231
Session 4a
Algorithms for Dominating Set in Disk Graphs: Breaking the log n Barrier Matt Gibson Imran A. Pirwani 243
Minimum Vertex Cover in Rectangle Graphs Reuven Bar- Yehuda Danny Hermelin Dror Rawitz 255
Feedback Vertex Sets in Tournaments Serge Gaspers Matthias Mnich 267
Session 4b
n-Level Graph Partitioning Vitaly Osipov Peter Sanders 278
Fast Routing in Very Large Public Transportation Networks Using Transfer Patterns Hannah Bast Erik Carlsson Arno Eigenwillig Robert Geisberger Chris Harrelson Veselin Raychev Fabien Viger 290
Finding the Diameter in Real-World Graphs: Experimentally Turning a Lower Bound into an Upper Bound Pierluigi Crescenzi Roberto Grossi Claudio Imbrenda Leonardo Lanzi Andrea Marino 302
Session 5a
Budgeted Red-Blue Median and Its Generalizations MohammadTaghi Hajiaghayi Rohit Khandekar Guy Kortsarz 314
All Ternary Permutation Constraint Satisfaction Problems Parameterized above Average Have Kernels with Quadratic Numbers of Variables Gregory Gutin Leo van Iersel Matthias Mnich Anders Yeo 326
Strong Formulations for the Multi-module PESP and a Quadratic Algorithm for Graphical Diophantine Equation Systems Laura Galli Sebastian Stiller 338
Robust Algorithms for Sorting Railway Cars Christina Büsing Jens Maue 350
Session 5b
Cloning Voronoi Diagrams via Retroactive Data Structures Matthew T. Dickerson David Eppstein Michael T. Goodrich 362
A Unified Approach to Approximate Proximity Searching Sunil Arya Guilherme D. da Fonseca David M. Mount 374
Spatio-temporal Range Searching over Compressed Kinetic Data Sorelle A. Friedler David M. Mount 386
Constructing the Exact Voronoi Diagram of Arbitrary Lines in Three-Dimensional Space: with Fast Point-Location Michael Hemmer Ophir Setter Dan Halperin 398
Invited Talk
Local Graph Exploration and Fast Property Testing Artur Czumaj 410
Session 6a
A Fully Compressed Algorithm for Computing the Edit Distance of Run-Length Encoded Strings Kuan-Yu Chen Kun-Mao Chao 415
Fast Prefix Search in Little Space, with Applications Djamal Belazzougui Paolo Boldi Rasmus Pagh Sebastiano Vigna 427
On the Huffman and Alphabetic Tree Problem with General Cost Functions Hiroshi Fujiwara Tobias Jacobs 439
Medium-Space Algorithms for Inverse BWT Juha Kärkkäinen Simon J. Puglisi 451
Session 6b
Median Trajectories Kevin Buchin Maike Buchin Marc van Kreveld Maarten Löffler Rodrigo I. Silveira Carola Wenk Lionov Wiratma 463
Optimal Cover of Points by Disks in a Simple Polygon Haim Kaplan Matthew J. Katz Gila Morgenstern Micha Sharir 475
Stability of ε-Kernels Pankaj K. Agarwal Jeff M. Phillips Hai Yu 487
The Geodesic Diameter of Polygonal Domains Sang Won Bae Matias Korman Yoshio Okamoto 500
Session 7a
Polyhedral and Algorithmic Properties of Quantified Linear Programs Ulf Lorenz Alexander Martin Jan Wolf 512
Approximating Parameterized Convex Optimization Problems Joachim Giesen Martin Jaggi Sören Laue 524
Approximation Schemes for Multi-Budgeted Independence Systems Fabrizio Grandoni Rico Zenklusen 536
Session 7b
Algorithmic Meta-theorems for Restrictions of Treewidth Michael Lampis 549
Determining Edge Expansion and Other Connectivity Measures of Graphs of Bounded Genus Viresh Patel 561
Constructing the R* Consensus Tree of Two Trees in Subcubic Time Jesper Jansson Wing-Kin Sung 573
Author Index 585
