Search ACM DL

Search Issue

enter search term and/or author name

**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...