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 Worst-Case 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 Private-Cache 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 re-evaluation 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/17-Approximation Algorithm for the Stable Marriage Problem with One-Sided Ties
K. Iwama, S. Miyazaki and H. Yanagisawa
Pairing Heaps with Costless Meld
A. Elmasry
 
 
Strongly Stable Assignment
N. Chen and A. Ghosh
Top-k 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 Wulff-Nilsen
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 Real-Time Multiprocessor Task Systems (best paper)
Vincenzo Bonifaci and Alberto Marchetti-Spaccamela