ACM DL

Journal of the ACM (JACM)

Menu

Search Issue
enter search term and/or author name

Archive


Journal of the ACM (JACM), Volume 58 Issue 3, May 2011

On the competitive ratio of evaluating priced functions
Ferdinando Cicalese, Eduardo Sany Laber
Article No.: 9
DOI: 10.1145/1970392.1970393

Let f be a function on a set of variables V. For each xV, let c(x) be the cost of reading the value of x. An algorithm for evaluating f is a strategy for adaptively identifying and reading a...

Market equilibrium under separable, piecewise-linear, concave utilities
Vijay V. Vazirani, Mihalis Yannakakis
Article No.: 10
DOI: 10.1145/1970392.1970394

We consider Fisher and Arrow--Debreu markets under additively separable, piecewise-linear, concave utility functions and obtain the following results. For both market models, if an equilibrium exists, there is one that is rational and can be...

Robust principal component analysis?
Emmanuel J. Candès, Xiaodong Li, Yi Ma, John Wright
Article No.: 11
DOI: 10.1145/1970392.1970395

This article is about a curious phenomenon. Suppose we have a data matrix, which is the superposition of a low-rank component and a sparse component. Can we recover each component individually? We prove that under some suitable assumptions,...

Introduction to JACM invited article
Victor Vianu
Article No.: 12
DOI: 10.1145/1970392.1970396

Estimating PageRank on graph streams
Atish Das Sarma, Sreenivas Gollapudi, Rina Panigrahy
Article No.: 13
DOI: 10.1145/1970392.1970397

This article focuses on computations on large graphs (e.g., the web-graph) where the edges of the graph are presented as a stream. The objective in the streaming model is to use small amount of memory (preferably sub-linear in the number of nodes...