Schedule (Wednesday, 8th September)
8:30  9:00  Morning Coffee  
09:00  9:50 
Invited Speaker:
Paolo Ferragina
Data Structures: TIme, I/Os, Entropy, Joules! Ulrich Meyer 

10:00  10:20  Coffee Break  
10:20  12:00 
Session 8a (ESA) Khaled Elbassioni 
Session 8b (ESA) Jeff Philips 
Session 8c (WABI) Sebastian Bocker 
Weighted Congestion Games: Price of Anarchy, Universal WorstCase Examples, Tightness K. Bhawalkar, M. Gairing and T. Roughgarden 
Frechet Distance of Surfaces: Some Simple Hard Cases K. Buchin, M. Buchin and A. Schulz 
Haplotype Inference on Pedigrees with Recombinations Y. Pirola, P. Bonizzoni and T. Jiang 

Computing Pure Nash and Strong Equilibria in Bottleneck Congestion Games T. Harks, M. Hoefer, M. Klimm and A. Skopalik 
Geometric Algorithms for PrivateCache Chip Multiprocessors D. Ajwani, N. Sitchinava and N. Zeh 
Data structures for accelerating Tanimoto queries on real valued vectors T.G. Kristensen and C.N.S. Pedersen 

Combinatorial Auctions with Verification are Tractable P. Krysta and C. Ventre 
Volume in General Metric Spaces I. Abraham, Y. Bartal, O. Neiman and L. Schulman 
Swiftly Computing Center Strings F. Hufsky, L. Kuchenbecker, K. Jahn, J. Stoye and S. Böcker 

How to Allocate Goods in an Online Market? Y. Azar, N. Buchbinder and K. Jain 
Shortest Cut Graph of a Surface with Prescribed Vertex Set É. Colin de Verdière 
Pair HMM based gap statistics for reevaluation of indels in alignments with affine gap penalties A. Schönhuth, R. Salari and S.C. Sahinalp 

12:00  13:30  Lunch  
13:30  15:10 
Session 9a (ESA) Mikko Koivisto 
Session 9b (ESA) Lars Engebretsen 
Session 9c (WABI) Vincent Moulton 
Induced matchings in subcubic planar graphs R. Kang, M. Mnich and T. Müller 
Data Structures for Storing Small Sets in the Bitprobe Model J. Radhakrishnan, S. Shah and S. Shannigrahi 
Speeding up Exact Motif Discovery by Bounding the Expected Clump Size T. Marschall and S. Rahmann 

Robust Matchings and Matroid Intersections Y. Kobayashi, R. Fujita and K. Makino 
On Space Efficient Two Dimensional Range Minimum Data Structures G.S. Brodal, P. Davoodi and S.S. Rao 
Quantifying the strength of natural selection of a motif sequence C.H. Yeang 

A 25/17Approximation Algorithm for the Stable Marriage Problem with OneSided Ties K. Iwama, S. Miyazaki and H. Yanagisawa 
Pairing Heaps with Costless Meld A. Elmasry 


Strongly Stable Assignment N. Chen and A. Ghosh 
Topk Ranked Document Search in General Text Databases S. Culpepper, G. Navarro, S. Puglisi and A. Turpin 


15:10  15:30  Coffee Break  
15:30  16:20 
ESA Best Paper Session + Closing Mark de Berg 

Shortest Paths in Planar Graphs with Real Lengths in O(n log2(n) / loglog n) (best student paper) Shay Mozes and Christian WulffNilsen 

When LP is the Cure for Your Matching Woes: Improved Bounds for Stochastic Matchings (best paper) Nikhil Bansal, Anupam Gupta, Jian Li, Julian Mestre, Viswanath Nagarajan and Atri Rudra 

Feasibility Analysis of Sporadic RealTime Multiprocessor Task Systems (best paper) Vincenzo Bonifaci and Alberto MarchettiSpaccamela 