40 citations · 79 across the 9 of their papers we have counts for
4 papers · 1 filter
Online Stochastic Matching: Beating 1-1/e
Jon Feldman, Aranyak Mehta, Vahab Mirrokni +1
We study the online stochastic bipartite matching problem, in a form motivated by display ad allocation on the Internet. In the online, but adversarial case, the celebrated result…
Relative-Error CUR Matrix Decompositions
Petros Drineas, Michael W. Mahoney, S. Muthukrishnan
Many data analysis applications deal with large matrices and involve approximating the matrix using a small number of ``components.'' Typically, these components are linear combina…
Radix Sorting With No Extra Space
Gianni Franceschini, S. Muthukrishnan, Mihai Patrascu
It is well known that n integers in the range [1,n^c] can be sorted in O(n) time in the RAM model using radix sorting. More generally, integers in any range [1,U] can be sorted in…
Estimating Aggregate Properties on Probabilistic Streams
Andrew McGregor, S. Muthukrishnan
The probabilistic-stream model was introduced by Jayram et al. \cite{JKV07}. It is a generalization of the data stream model that is suited to handling ``probabilistic'' data where…