Algorithms -- ESA 2010, Part II : 18th Annual European Symposium, Liverpool, UK, September 6-8, 2010, Proceedings

by De Berg, Mark; Meyer, Ulrich

• ISBN13: 9783642157806
• ISBN10: 3642157807
• Edition: 1st
• Format: Paperback
• Copyright: 2010-09-20
• Publisher: Springer-Verlag New York Inc

Summary

This book constitutes the proceedings of the 18th Annual European Symposium on Algorithms, held in Liverpool, UK in September 2010.

Table of Contents

Invited Talk
Data Structures: Time, I/Os, Entropy, Joules!	p. 1
Session 8a
Weighted Congestion Games: Price of Anarchy, Universal Worst-Case Examples, and Tightness	p. 17
Computing Pure Nash and Strong Equilibria in Bottleneck Congestion Games	p. 29
Combinatorial Auctions with Verification Are Tractable	p. 39
How to Allocate Goods in an Online Market?	p. 51
Session 8b
Fréchet Distance of Surfaces: Some Simple Hard Cases	p. 63
Geometric Algorithms for Private-Cache Chip Multiprocessors	p. 75
Volume in General Metric Spaces	p. 87
Shortest Cut Graph of a Surface with Prescribed Vertex Set	p. 100
Session 9a
Induced Matchings in Subcubic Planar Graphs	p. 112
Robust Matchings and Matroid Intersections	p. 123
A 25/17-Approximation Algorithm for the Stable Marriage Problem with One-Sided Ties	p. 135
Strongly Stable Assignment	p. 147
Session 9b
Data Structures for Storing Small Sets in the Bitprobe Model	p. 159
On Space Efficient Two Dimensional Range Minimum Data Structures	p. 171
Pairing Heaps with Costless Meld	p. 183
Top-k Ranked Document Search in General Text Databases	p. 194
Best-Paper Session
Shortest Paths in Planar Graphs with Real Lengths in O(n log2 n/log log n) Time	p. 206
When LP Is the Cure for Your Matching Woes: Improved Bounds for Stochastic Matchings	p. 218
Feasibility Analysis of Sporadic Real-Time Multiprocessor Task Systems	p. 230
Author Index	p. 243
Table of Contents provided by Ingram. All Rights Reserved.