enter search term and/or author name
Tight bounds for asynchronous randomized consensus
Hagit Attiya, Keren Censor
Article No.: 20
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...
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
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
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...
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...