ACM DL

Journal of the ACM (JACM)

Menu

Search Issue
enter search term and/or author name

Archive


Journal of the ACM (JACM), Volume 56 Issue 4, June 2009

Graph partitioning using single commodity flows
Rohit Khandekar, Satish Rao, Umesh Vazirani
Article No.: 19
DOI: 10.1145/1538902.1538903

We show that the sparsest cut in graphs with n vertices and m edges can be approximated within O(log2 n) factor in Õ(m + n3/2) time using polylogarithmic single commodity max-flow...

Unbalanced expanders and randomness extractors from Parvaresh--Vardy codes
Venkatesan Guruswami, Christopher Umans, Salil Vadhan
Article No.: 20
DOI: 10.1145/1538902.1538904

We give an improved explicit construction of highly unbalanced bipartite expander graphs with expansion arbitrarily close to the degree (which is polylogarithmic in the number of vertices). Both the degree and the number of right-hand vertices are...

On the bias of traceroute sampling: Or, power-law degree distributions in regular graphs
Dimitris Achlioptas, Aaron Clauset, David Kempe, Cristopher Moore
Article No.: 21
DOI: 10.1145/1538902.1538905

Understanding the graph structure of the Internet is a crucial step for building accurate network models and designing efficient algorithms for Internet applications. Yet, obtaining this graph structure can be a surprisingly difficult task, as...

Empirical hardness models: Methodology and a case study on combinatorial auctions
Kevin Leyton-Brown, Eugene Nudelman, Yoav Shoham
Article No.: 22
DOI: 10.1145/1538902.1538906

Is it possible to predict how long an algorithm will take to solve a previously-unseen instance of an NP-complete problem? If so, what uses can be found for models that make such predictions? This article provides answers to these...

Quantifying inefficiency in cost-sharing mechanisms
Tim Roughgarden, Mukund Sundararajan
Article No.: 23
DOI: 10.1145/1538902.1538907

In a cost-sharing problem, several participants with unknown preferences vie to receive some good or service, and each possible outcome has a known cost. A cost-sharing mechanism is a protocol that decides which participants are allocated a good...

The complexity of obstruction-free implementations
Hagit Attiya, Rachid Guerraoui, Danny Hendler, Petr Kuznetsov
Article No.: 24
DOI: 10.1145/1538902.1538908

Obstruction-free implementations of concurrent objects are optimized for the common case where there is no step contention, and were recently advocated as a solution to the costs associated with synchronization without locks. In this...