This book constitutes the proceedings of the 18th Annual European Symposium on Algorithms, held in Liverpool, UK in September 2010.
Author(s): Paolo Ferragina (auth.), Mark de Berg, Ulrich Meyer (eds.)
Series: Lecture Notes in Computer Science 6347 : Theoretical Computer Science and General Issues
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2010
Language: English
Pages: 245
Tags: Algorithm Analysis and Problem Complexity; Computer Communication Networks; Discrete Mathematics in Computer Science; Computer Graphics; Numeric Computing; Data Structures
Front Matter....Pages -
Data Structures: Time, I/Os, Entropy, Joules!....Pages 1-16
Weighted Congestion Games: Price of Anarchy, Universal Worst-Case Examples, and Tightness....Pages 17-28
Computing Pure Nash and Strong Equilibria in Bottleneck Congestion Games....Pages 29-38
Combinatorial Auctions with Verification Are Tractable....Pages 39-50
How to Allocate Goods in an Online Market?....Pages 51-62
Fréchet Distance of Surfaces: Some Simple Hard Cases....Pages 63-74
Geometric Algorithms for Private-Cache Chip Multiprocessors....Pages 75-86
Volume in General Metric Spaces....Pages 87-99
Shortest Cut Graph of a Surface with Prescribed Vertex Set....Pages 100-111
Induced Matchings in Subcubic Planar Graphs....Pages 112-122
Robust Matchings and Matroid Intersections....Pages 123-134
A 25/17-Approximation Algorithm for the Stable Marriage Problem with One-Sided Ties....Pages 135-146
Strongly Stable Assignment....Pages 147-158
Data Structures for Storing Small Sets in the Bitprobe Model....Pages 159-170
On Space Efficient Two Dimensional Range Minimum Data Structures....Pages 171-182
Pairing Heaps with Costless Meld....Pages 183-193
Top- k Ranked Document Search in General Text Databases....Pages 194-205
Shortest Paths in Planar Graphs with Real Lengths in O ( n log 2 n /loglog n ) Time....Pages 206-217
When LP Is the Cure for Your Matching Woes: Improved Bounds for Stochastic Matchings....Pages 218-229
Feasibility Analysis of Sporadic Real-Time Multiprocessor Task Systems....Pages 230-241
Back Matter....Pages -
