SPAA 2012 Conference Program


Contents:



Keynote Addresses

Ravi Rajwar.
In Search of Parallel Dimensions

Doug Lea.
Abstraction failures in concurrent programming.

List of Accepted Papers

Regular papers:

Klaus Jansen.
A (3/2+\epsilon) approximation algorithm for scheduling malleable and non-malleable parallel tasks

Moran Feldman, Liane Lewin-Eytan and Seffi Naor.
Hedonic Clustering Games

Jurek Czyzowicz, Adrian Kosowski and Andrzej Pelc.
Time vs. space trade-offs for rendezvous in trees

James Aspnes, Hagit Attiya, Keren Censor-Hillel and Danny Hendler.
Lower Bounds for Restricted-Use Objects

John Augustine, Ioannis Caragiannis, Angelo Fanelli and Christos Kalaitzis.
Enforcing efficient equilibria in network design games via subsidies

Ho-Leung Chan, Sze-Hang Chan, Tak-Wah Lam, Lap-Kei Lee and Jianqiao Zhu.
Non-clairvoyant Weighted Flow Time Scheduling with Rejection Penalty

Anastasia Braginsky and Erez Petrank.
A Lock-Free B+tree

Fengguang Song and Jack Dongarra.
A Scalable Framework for Heterogeneous GPU-Based Clusters

Elad Gidron, Idit Keidar, Dmitri Perelman and Yonathan Perez.
SALSA: Scalable and Low Synchronization NUMA-aware Algorithm for Producer-Consumer Pools

Johannes Dams, Martin Hoefer and Thomas Kesselheim.
Scheduling in Wireless Networks with Rayleigh-Fading Interference

Florent Becker, Adrian Kosowski, Nicolas Nisse, Ivan Rapaport and Karol Suchan.
Allowing each node to communicate only once in a distributed system: shared whiteboard models.

I-Ting Lee, Aamir Shafi and Charles Leiserson.
Memory-Mapping Support for Reducer Hyperobjects

Grey Ballard, James Demmel, Olga Holtz, Benjamin Lipshitz and Oded Schwartz.
Communication-Optimal Parallel Algorithm for Strassenīs Matrix Multiplication

Richard Peng and Kanat Tangwongsan.
Faster and Simpler Width-Independent Parallel Algorithms for Positive Semidefinite Programming

Guy Blelloch, Anupam Gupta and Kanat Tangwongsan.
Parallel Probabilistic Tree Embeddings, k-Median, and Buy-at-Bulk Network Design

Guy Blelloch, Harsha Vardhan Simhadri and Kanat Tangwongsan.
Parallel and I/O Efficient Algorithms for Set Covering Problems

Stephan Holzer, Thomas Locher, Yvonne-Anne Pignolet and Roger Wattenhofer.
Deterministic Multi-Channel Information Exchange

Darko Petrovic, Omid Shahmirzadi, Thomas Ropars and Andre Schiper.
High-Performance RMA-Based Broadcast on the Intel SCC

Adrian Ogierman and Robert Elsaesser.
The Impact of the Power Law Exponent on the Behavior of a Dynamic Epidemic Type Process

Barbara Kempkes, Peter Kling and Friedhelm Meyer Auf der Heide.
Optimal and competitive runtime bounds for continuous, local gathering of mobile robots

Christian Ortolf and Christian Schindelhauer.
Online Multi-Robot Exploration of Grid Graphs with Rectangular Obstacles

Dan Alistarh, Rachid Guerraoui, Giuliano Losa and Petr Kuznetsov.
On the Complexity of Composing Concurrent Algorithms

Atish Das Sarma, Michael Dinitz and Gopal Pandurangan.
Efficient Computation of Distance Sketches in Distributed Networks

Guy Blelloch, Jeremy Fineman and Julian Shun.
Greedy Sequential Maximal Independent Set and Matching are Parallel on Average

Yujie Liu, Stephan Diestelhorst and Michael Spear.
Delegation and Nesting in Best Effort Hardware Transactional Memory

Shane V. Howley and Jeremy Jones.
A Non-Blocking Internal Binary Search Tree

Kunal Agrawal, Jeremy Fineman, Jordan Krage, Charles Leiserson and Sivan Toledo.
Cache-Conscious Scheduling of Streaming Applications

Bernard Haeupler, Gopal Pandurangan, David Peleg, Rajmohan Rajaraman and Zhifeng Sun.
Discovery through Gossip

Nodari Sitchinava and Norbert Zeh.
A Parallel Buffer Tree

Navendu Jain, Ishai Menache, Joseph Naor and Jonathan Yaniv.
Near-Optimal Scheduling Mechanisms for Deadline-Sensitive Jobs in Large Computing Clusters

Jun Shirako, Nick Vrvilo, Eric Mercer and Vivek Sarkar.
Design, Verification and Applications of a New Read-Write Lock Algorithm

Brief announcements:

Claire Ralph, Vitus Leung and William Mclendon.
Subgraph Isomorphism in a Multithreaded Shared Memory Architecture

Neeraj Sharma and Sandeep Sen.
Efficient cache oblivious algorithms for randomized divide-and-conquer on the multicore model

Grey Ballard, James Demmel, Olga Holtz, Benjamin Lipshitz and Oded Schwartz.
Strong Scaling of Matrix Multiplication Algorithms and Memory-Independent Communication Lower Bounds

Henry Lin and Frans Schalekamp.
On the Complexity of the Minimum Latency Scheduling Problem on the Euclidean Plane

Kamil Rocki and Reiji Suda.
An efficient GPU implementation of the iterative hill climbing based TSP solver

Ahmed Elnably and Peter Varman.
Application-Sensitive QoS Scheduling in Storage Servers

Aparna Chandramowlishwaran, Jee Choi, Kamesh Madduri and Richard Vuduc.
Towards a Communication Optimal Fast Multipole Method and its Implications at Exascale

Guy Blelloch, Jeremy Fineman, Phillip Gibbons, Aapo Kyrola, Julian Shun, Harsha Vardhan Simhadri and Kanat Tangwongsan.
The Problem Based Benchmark Suite

James Edwards and Uzi Vishkin.
Speedups for Parallel Graph Triconnectivity