enter search term and/or author name
On the competitive ratio of evaluating priced functions
Ferdinando Cicalese, Eduardo Sany Laber
Article No.: 9
Let f be a function on a set of variables V. For each x ∈ V, 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
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...
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,...
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...