SPAA 2012 Conference Program
Contents:
Keynote Addresses
Ravi Rajwar.
In Search of Parallel Dimensions
Doug Lea.
Abstraction failures in concurrent programming.
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