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

by Mark de Berg (Editor), Ulrich Meyer (Editor)

Overview

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

Product Details

ISBN-13:	9783642157806
Publisher:	Springer Berlin Heidelberg
Publication date:	11/04/2010
Series:	Lecture Notes in Computer Science , #6347
Edition description:	2010
Pages:	245
Product dimensions:	6.10(w) x 9.30(h) x 0.60(d)

Table of Contents

Invited Talk

Data Structures: Time, I/Os, Entropy, Joules! Paolo Ferragina 1

Session 8a

Weighted Congestion Games: Price of Anarchy, Universal Worst-Case Examples, and Tightness Kshipra Bhawalkar Martin Gairing Tim Roughgarden 17

Computing Pure Nash and Strong Equilibria in Bottleneck Congestion Games Tobias Harks Martin Hoefer Max Klimm Alexander Skopalik 29

Combinatorial Auctions with Verification Are Tractable Piotr Krysta Carmine Ventre 39

How to Allocate Goods in an Online Market? Yossi Azar Niv Buchbinder Kamal Jain 51

Session 8b

Fréchet Distance of Surfaces: Some Simple Hard Cases Kevin Buchin Maike Buchin André Schulz 63

Geometric Algorithms for Private-Cache Chip Multiprocessors Deepak Ajwani Nodari Sitchinava Norbert Zeh 75

Volume in General Metric Spaces Ittai Abraham Yair Bartal Ofer Neiman Leonard J. Schulman 87

Shortest Cut Graph of a Surface with Prescribed Vertex Set Éric Colin de Verdière 100

Session 9a

Induced Matchings in Subcubic Planar Graphs Ross J. Kang Matthias Mnich Tobias Müller 112

Robust Matchings and Matroid Intersections Ryo Fujita Yusuke Kobayashi Kazuhisa Makino 123

A 25/17-Approximation Algorithm for the Stable Marriage Problem with One-Sided Ties Kazuo Iwama Shuichi Miyazaki Hiroki Yanagisawa 135

Strongly Stable Assignment Ning Chen Arpita Ghosh 147

Session 9b

Data Structures for Storing Small Sets in the Bitprobe Model Jaikumar Radhakrishnan Smit Shah Saswata Shannigrahi 159

On Space Efficient Two Dimensional Range Minimum Data Structures Gerth Stølting Brodal Pooya Davoodi S. Srinivasa Rao 171

Pairing Heaps with Costless Meld Amr Elmasry 183

Top-k Ranked Document Search in General Text Databases J. Shane Culpepper Gonzalo Navarro Simon J. Puglisi Andrew Turpin 194

Best-Paper Session

Shortest Paths in Planar Graphs with Real Lengths in O(n log² n/log log n) Time Shay Mozes Christian Wulff-Nilsen 206

When LP Is the Cure for Your Matching Woes: Improved Bounds for Stochastic Matchings Nikhil Bansal Anupam Gupta Jian Li Julián Mestre Viswanath Nagarajan Atri Rudra 218

Feasibility Analysis of Sporadic Real-Time Multiprocessor Task Systems Vincenzo Bonifaci Alberto Marchetti-Spaccamela 230

Author Index 243