Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 55 Issue 5, October 2008

Tight bounds for asynchronous randomized consensus
Hagit Attiya, Keren Censor
Article No.: 20
DOI: 10.1145/1411509.1411510

A distributed consensus algorithm allows n processes to reach a common decision value starting from individual inputs. Wait-free consensus, in which a process always terminates within a finite number of its own steps, is impossible...

A fixed-parameter algorithm for the directed feedback vertex set problem
Jianer Chen, Yang Liu, Songjian Lu, Barry O'sullivan, Igor Razgon
Article No.: 21
DOI: 10.1145/1411509.1411511

The (parameterized) FEEDBACK VERTEX SET problem on directed graphs (i.e., the DFVS problem) is defined as follows: given a directed graph G and a parameter k, either construct a feedback vertex set of at most k vertices in...

Market equilibrium via a primal--dual algorithm for a convex program
Nikhil R. Devanur, Christos H. Papadimitriou, Amin Saberi, Vijay V. Vazirani
Article No.: 22
DOI: 10.1145/1411509.1411512

We give the first polynomial time algorithm for exactly computing an equilibrium for the linear utilities case of the market model defined by Fisher. Our algorithm uses the primal--dual paradigm in the enhanced setting of KKT conditions and convex...

Aggregating inconsistent information: Ranking and clustering
Nir Ailon, Moses Charikar, Alantha Newman
Article No.: 23
DOI: 10.1145/1411509.1411513

We address optimization problems in which we are given contradictory pieces of input information and the goal is to find a globally consistent solution that minimizes the extent of disagreement with the respective inputs. Specifically, the...

Random sampling from a search engine's index
Ziv Bar-Yossef, Maxim Gurevich
Article No.: 24
DOI: 10.1145/1411509.1411514

We revisit a problem introduced by Bharat and Broder almost a decade ago: How to sample random pages from the corpus of documents indexed by a search engine, using only the search engine's public interface? Such a primitive is particularly...