Table of Contents
Optimal Exploration of Terrains with Obstacles Jurek Czyzowicz David Ilcinkas Arnaud Labourel Andrzej Pelc 1
Reconstructing a Simple Polygon from Its Angles Yann Disser Matúš Mihalák Peter Widmayer 13
Semidefinite Programming and Approximation Algorithms: A Survey (Invited Talk) Sanjeev Arora 25
Strictly-Regular Number System and Data Structures Amr Elmasry Claus Jensen Jyrki Katajainen 26
An O(log log n)-Competitive Binary Search Tree with Optimal Worst-Case Access Times Prosenjit Bose Karim Douïeb Vida Dujmovic Rolf Fagerberg 38
The Emergence of Sparse Spanners and Greedy Well-Separated Pair Decomposition Jie Gao Dengpan Zhou 50
A Bottom-Up Method and Fast Algorithms for Max Independent Set Nicolas Bourgeois Bruno Escoffier Vangelis Th. Paschos Johan M.M. van Rooij 62
Capacitated Domination Faster Than O(2n) Marek Cygan Marcin Pilipczuk Jakub Onufry Wojtaszczyk 74
Isomorphism for Graphs of Bounded Feedback Vertex Set Number Stefan Krastsch Pascal Schweitzer 81
On Feedback Vertex Set New Measure and New Structures Yixin Cao Jianer Chen Yang Liu 93
Conflict-Free Coloring Made Stronger Elad Horev Roi Krakovski Shakhar Smorodinsky 105
Polychromatic Coloring for Half-Planes Shakhar Smorodinsky Yelena Yudistsky 118
A3/2-Approximation Algorithm for Multiple Depot Multiple Traveling Salesman Problem (Extended Abstract) Zhou Xu Brian Rodrigues 127
Minimum and Maximum against k Lies Michael Hoffmann Jirí Matoušek Yoshio Okamoto Philipp Zumstein 139
Feasible and Accurate Algorithms for Covering Semidefinite Programs Garud Iyengar David J. Philips Cliff Stein 150
The Quantitative Analysis of User Behavior Online - Data, Models and Algorithms (Invited Talk) Prabhakar Raghavan 163
Systems of Linear Equations over F2 and Problems Parameterized above Average Robert Crowston Gregory Gutin Mark Jones Eun Jung Kim Imre Z. Ruzsa 164
Capacitated max-Batching with Interval Graph Compatibilities Tim Nonner 176
A Weakly Robust PTAS for Minimum Clique Partition in Unit Disk Graphs (Extended Abstract) Imran A. Pirwani Mohammed R. Salavatipour 188
Representing a Functional Curve by Curves with Fewer Peaks Danny Z. Chen Chao Wang Haitao Wang 200
Bregman Clustering for Separable Instances Marcel R. Ackermann Johannes Blö 212
Improved Methods for Generating Quasi-gray Codes Prosenjit Bose Paz Carmi Dana Jansens Anil Maheshwari Pat Morin Michiel Smid 224
The MST of Symmetric Dist Graphs Is Light A. Karim Abu-Affash Rom Aschner Paz Carmi Matthew J. Katz 236
Vector Bin Packing with Multiple-Choice (Extended Abstract) Boaz Patt-Shamir Dror Rawitz 248
Bin Packing with Fixed Number of Bins Revisited Klalus Jansen Stefan Kratsch Dániel Marx Ildikó Schlotter 260
Cops and Robber Game without Recharging Fedor V. Fomin Petr A. Golovach Daniel Lokshtanov 273
Path Schematization for Route Sketches Daniel Delling Andreas Gemsa Martin Nöllenburg Thomas Pajor 285
Approximation Algorithms for Free-Label Maximization Mark de Berg Dirk H.P. Gerrits 297
Phase Transitions in Sampling Algorithms and the Underlying Random Structures Dana Randall 309
Polynomial Kernels for Hard Problems on Disk Graphs Bart Jansen 310
Faster Parameterized Algorithms for Minor Containment Isolde Adler Frederic Dorn Fedor V. Fomin Ignasi Sau Dimitrios M. Thilikos 322
Fixed-Parameter Algorithms for Cochromatic Number and Disjoint Rectangle Stabbing Pinar Heggernes Dieter Kratsch Daniel Lokshtanov Venkatesh Raman Saket Saurabh 334
Dispatching Equal-Length Jobs to Parallel Machines to Maximize Throughput David P. Bunde Michael H. Goldwasser 346
Online Function Tracking with Generalized Penalties Marcin Bienkowski Stefan Schmid 359
Better Bounds on Online Unit Clustering Martin R. Ehmsen Kim S. Larsen 371
Online Selection of Intervals and t-Intervals Unnar Th. Bachmann Magnús M. Halldórsson Hadas Shachnai 383
Approximating the Maximum 3- and 4-Edge-Colorable Subgraph (Extended Abstract) Marcin Kaminski Lukasz Kowalik 395
Improved Algorithm for Degree Bounded Survivable Network Design Problem Anand Louis Nisheeth K. Vishnoi 408
Minimizing the Diameter of a Network Using Shortcut Edges Erik D. Demaine Morteza Zadimoghaddam 420
Author Index 433
