SPAA 2005 Conference Program
Contents:
Regular papers (in no particular order):
Coloring Unstructured Radio Networks
Thomas Moscibroda and Roger Wattenhofer
Randomized Queue Management for DiffServ
Nir Andelman
Is partial quantum search of a database any easier?
Lov K Grover and Jaikumar Radhakrishnan
Windows Scheduling of Arbitrary Length Jobs on Parallel Machines
Amotz Bar-Noy and Richard E. Ladner and Tami Tamir and Tammy VanDeGrift
Admission Control to Minimize Rejections and Online Set Cover with Repetitions
Noga Alon and Yossi Azar and Shai Gutner
Name Independent Routing for Growth Bounded Networks
Ittai Abraham and Dahlia Malkhi
Parallel Scheduling of Complex Dags under Uncertainty
Grzegorz Malewicz
Randomization does not reduce the average delay in parallel packet switches
Hagit Attiya and David Hay
On Distributed Smooth Scheduling
Ami Litman and Shiri Moran-Schein
The Expansion and Mixing Time of Skip Graphs with Applications
Jamse Aspnes and Udi Wieder
Decentralized Algorithms using both Local and Random Probes for P2P Load Balancing
Krishnaram Kenthapadi and Gurmeet Singh Manku
Fast Construction of Overlay Networks
Dana Angluin and James Aspnes and Jiang Chen and Yinghua Wu and Yitong Yin
Traffic Engineering of Management Flows by Link Augmentations on Confluent Trees
Randeep S. Bhatia and Nicole Immorlica and Tracy Kimbrel and Vahab S. Mirrokni and Seffi Naor and Baruch Schieber
Broadcasting on Networks of Workstations
Samir Khuller and Yoo-Ah Kim and Yung-Chun (Justin) Wan
Lexicographic QoS Scheduling for Parallel I/O
Ajay Gulati and Peter Varman
Dynamic Page Migration with Stochastic Requests
Marcin Bienkowski
Adversarial Contention Resolution for Simple Channels
Michael A. Bender and Martin Farach-Colton and Simai He and Bradley C. Kuszmaul and Charles E. Leiserson
An Adaptive Power Conservation Scheme for Heterogeneous Wireless Sensor
Ioannis Chatzigiannakis and Athanassios Kinalis and Sotiris Nikoletseas
Weighted Distributed Hash Tables
Christian Schindelhauer and Gunnar Schomaker
Peer-to-Peer Networks based on Random Transformations of Connected Regular Undirected Graphs
Peter Mahlmann and Christian Schindelhauer
A Truthful Mechanism for the Non-Utilitarian Minimum Radius Spanning Tree Problem
Guido Proietti and Peter Widmayer
Scheduling Malleable Tasks with Precedence Constraints
Klaus Jansen and Hu Zhang
Irrigating Ad Hoc Networks in Constant Time
D. Dubhashi and O. Haggstrom and C. Johansson and A. Panconesi and M. Sozio
Constant Density Spanners for Wireless Ad-Hoc Networks
Melih Onus and Andrea Richa and Kishore Kothapalli and Christian Scheideler
Radio Communication in Random Graphs
Robert Elsaesser and Leszek Gasieniec
Using Elimination to Implement Scalable FIFO Queues
Mark Moir and Daniel Nussbaum and Ori Shalev and Nir Shavit
Selfish Routing with Incomplete Information
Martin Gairing and Burkhard Monien and Karsten Tiemann
Oblivious Routing on Geometric Networks
Costas Busch and Malik Magdon-Ismail and Jing Xi
Processor Efficient Parallel Matching
Piotr Sankowski
Finding Effective Support-Tree Preconditioners
Bruce M. Maggs and Gary L. Miller and Ojas Parekh and R. Ravi and Shan Leung Maverick Woo
Concurrent Cache-Oblivious Search Trees
Michael A. Bender and Jeremy T. Fineman and Seth Gilbert and Bradley C. Kuszmaul
Dynamic Circular Work-Stealing Deque
David Chase and Yossi Lev
Value-Maximizing Deadline Scheduling and its Application to Animation Rendering
Eric Anderson and Dirk Beyer and Kamalika Chaudhuri and Terence Kelly and Norman Salazar and Cipriano Santos
Parallelizing Time With Polynomial Circuits
Ryan Williams
Efficient Algorithms for Verifying Memory Consistency
Chaiyasit Manovit and Sudheendra Hangal
Collaborate With Strangers To Find Own Preferences
Awerbuch and Azar and Lotker and Patt-Shamir and Tuttle
Brief announcments (in no particular order):
A Segmented Parallel-Prefix VLSI Circuit with Small Delays for Small Segments
Bradley C. Kuszmaul
A Forward Planning Situated Protocol for Data Propagation in Wireless Sensor Networks based on Swarm Intelligence Techniques
Ioannis Chatzigiannakis and Sotiris Nikoletseas
Autonomous Virtual Mobile Nodes
Shlomi Dolev and Seth Gilbert and Elad Schiller and Alex Shvartsman and Jennifer Welch
A Space Lower Bound for Name-Independent Compact Routing in Trees
Kofi A. Laing and Rajmohan Rajaraman
On Competitive Online Read-many Parallel Disks Scheduling
Rahul Shah and Peter J. Varman and Jeffrey Scott Vitter
To download the SPAA program, click here.
Christian Scheideler
Last modified: September 8, 2005