List of accepted papers for ESA 2008:


Alex Kesselman, Kirill Kogan and Michael Segal. 
Improved Competitive Performance Bounds for CIOQ Switches 

Peter Csorba, Cor Hurkens and Gerhard Woeginger. 
The Alcuin number of a graph 

Thanh Nguyen and Eva Tardos. 
Parallel Imaging Problem 

Natasha Shakhlevich, Akiyoshi Shioura and Vitaly Strusevich. 
Fast Divide-and-Conquer Algorithms for Preemptive Scheduling Problems with Controllable Processing Times—A Polymatroid Optimization Approach

Danny Z. Chen, Shuang Luan and Chao Wang. 
Coupled Path Planning, Region Optimization, and Applications in Intensity-Modulated Radiation Therapy 

Markus Blaeser, Bodo Manthey and Oliver Putz. 
Approximating Multi-Criteria Max-TSP 

Benjamin Hiller and Tjark Vredeveld. 
Probabilistic analysis of Online Bin Coloring algorithms via Stochastic Comparison 

Adam Kirsch, Michael Mitzenmacher and Udi Wieder. 
More Robust Hashing: Cuckoo Hashing with a Stash 

Anthony Labarre. 
Edit Distances and Factorisations of Even Permutations 

Leah Epstein and Elena Kleiman.
Selfish bin packing 

Lars Arge, Thomas Mølhave and Norbert Zeh. 
Cache-Oblivious Red-Blue Line Segment Intersection 

Pankaj Agarwal, Danny Z. Chen, Shashidhara Ganjugunte, Ewa Misiolek, Micha Sharir and Kai Tang. 
Stabbing Convex Polygons with a Segment or a Polygon 

Denis Charles and Kumar Chellapilla. 
Bloomier Filters: A second look 

Andrew Goldberg. 
The Partial Augment-Relabel Algorithm for the Maximum Flow Problem 

Stefan Felsner and Martin Pergel. 
Sorting Using Networks of Stacks and Queues 

Gill Barequet, David Eppstein, Michael Goodrich and Amir Vaxman. 
Straight Skeletons of Three-Dimensional Polyhedra 

Yann Lorion and Maik Weinard. 
The Effects of Local Randomness in the Adversarial Queueing Model 

Vasilis Samoladas. 
Improved BDD Algorithms for the Simulation of Quantum Circuits 

Herve Fournier and Antoine Vigneron. 
Fitting a step function to a point set 

Tom Coleman, James Saunderson and Anthony Wirth. 
A Local-Search 2-Approximation for 2-Correlation-Clustering 

Tobias Jacobs. 
On the Complexity of Optimal Hotlink Assignment 

Boris Aronov, Mark de Berg and Shripad Thite. 
The Complexity of Bisectors and Voronoi Diagrams on Realistic Terrains 

Julian Mestre and Samir Khuller. 
An Optimal Incremental Algorithm for Minimizing Lateness/Tardiness with Rejection 

Hamid Zarrabi-Zadeh. 
An Almost Space-Optimal Streaming Algorithm for Coresets in Fixed Dimensions 

Paul Bonsma and Frederic Dorn. 
Tight Bounds and Faster Algorithms for Directed Max-Leaf Problems 

Saverio Caminiti, Irene Finocchi and Rossella Petreschi. 
Engineering Tree Labeling Schemes: a Case Study on Least Common Ancestors 

Markus Chimani, Petra Mutzel and Immanuel Bomze. 
A New Approach to Exact Crossing Minimization 

Peter Sanders, Dominik Schultes and Christian Vetter. 
Mobile Route Planning 

Lee-Ad Gottlieb and Liam Roditty. 
An optimal dynamic spanner for doubling metric spaces 

Mark de Berg and Chris Gray. 
Decompositions and Boundary Coverings of Non-Convex Fat Polyhedra 

Herman Haverkort and Freek van Walderveen. 
Locality and bounding-box quality of two-dimensional space-filling curves 

Uriel Feige and Mohit Singh. 
Edge Coloring and Decompositions of Weighted Graphs 

Bojan Djordjevic, Joachim Gudmundsson, Anh Pham and Thomas Wolle. 
Detecting Regular Visit Patterns 

Christiane Lammersen and Christian Sohler. 
Facility Location in Dynamic Geometric Data Streams 

Fedor Fomin, Fabrizio Grandoni and Dieter Kratsch. 
Faster Steiner Tree Computation in Polynomial-Space 

Daniel Cederman and Philippas Tsigas. 
A Practical Quicksort Algorithm for Graphics Processors 

Vincenzo Bonifaci, Alberto Marchetti-Spaccamela and Sebastian Stiller. 
A Constant-Approximate Feasibility Test for Multiprocessor Real-Time Scheduling 

Jens Jaegerskuepper. 
Oblivious Randomized Direct Search for Real-Parameter Optimization 

Paolo Penna and Carmine Ventre. 
Collusion-Resistant Mechanisms with Verification Yielding Optimal Solutions 

Daniel Delling. 
Time-Dependent SHARC-Routing 

Rohit Khandekar, Guy Kortsarz, Vahab Mirrokni and Mohammad Salavatipour. 
Two-stage Robust Network Design with Exponential Scenarios 

Sunil Arya, David Mount, Antoine Vigneron and Jian Xia. 
Space-Time Tradeoffs for Proximity Searching in Doubling Spaces 

Tak-Wah Lam, Lap-Kei Lee, Isaac K. K. To and Prudence W.H. Wong. 
Speed Scaling Functions for Flow Time Scheduling based on Active Job Count 

Daisuke Okanohara and Kunihiko Sadakane. 
An Online Space-Efficient Algorithm for Searching the Longest Match String 

Spyros Angelopoulos. 
A Near-tight Bound for the Online Steiner Tree Problem in Graphs of Bounded Asymmetry 

Anke van Zuylen. 
Deterministic Sampling Algorithms 

Linqiao Zhang, Hazel Everett, Sylvain Lazard, Christophe Weibel and Sue Whitesides. 
On the size of the 3D visibility skeleton: experimental results 

Haim Kaplan and Nira Shafrir. 
Finding Path Minima in Incremental Unrooted Trees 

Wolfgang Bein, Kazuo Iwama and Jun Kawahara. 
Randomized Competitive Analysis for Two-Server Problems 

Zoltan Kiraly. 
Better and simpler approximation algorithms for the stable marriage problem 

Alon Efrat, Sandor P. Fekete, Poornananda R. Gaddehosur, Joseph S.B. Mitchell, Valentin Polishchuk and Jukka Suomela. 
Improved Approximation Algorithms for Relay Placement 

Pankaj Agarwal and Jeff Phillips. 
An Efficient Algorithm for Euclidian 2-Center with Outliers 

Leah Epstein and Asaf Levin. 
Improved randomized results for that interval selection problem 

Csaba Toth and Mashhood Ishaque. 
Relative Convex Hulls in Semi-Dynamic Subdivisions 

Stefan Schirra. 
How Reliable are Practical Point-in-Polygon Strategies? 

Sariel Har-Peled and S Muthukrishnan. 
Range Medians 

George Christodoulou, Elias Koutsoupias and Angelina Vidali. 
A characterization of 2-player mechanisms for scheduling 

Ajay Gulati and Peter Varman.
RFQ: Redemptive Fair Queuing 

Maxim Babenko and Alexander Karzanov. 
A Scaling Algorithm for Maximum Node-Capacitated Multiflow Problem 

Beat Gfeller. 
Faster Swap Edge Computation in Minimum Diameter Spanning Trees 

Umut Acar, Guy Blelloch, Kanat Tangwongsan and Duru Türkoglu. 
Robust Kinetic Convex Hulls in 3D 

Rene Sitters. 
Approximability of average completion time scheduling on unrelated machines 

Peyman Afshani. 
On Dominance Reporting in 3D 

Andreas Bley. 
An Integer Programming Algorithm for Routing Optimization in IP Networks 

Arash Farzan and Ian Munro. 
Succinct Representations of Arbitrary Graphs 

Tiffani Williams and Seung-Jin Sul. 
An Experimental Analysis of Robinson-Foulds Distance Matrix Algorithms 

Christian Bachmaier and Wolfgang Brunner. 
Linear Time Planarity Testing and Embedding of Strongly Connected Cyclic Level Graphs