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 |
|||
