(Near-)Linear-Time Randomized Algorithms for Row Minima in Monge Partial Matrices and Related Problems.

Timothy M. Chan

Published in: SODA (2021)

Keyphrases

related problems
randomized algorithms
worst case
approximation algorithms
data matrix
rows and columns
lower bound
practical problems
binary matrices
binary matrix
singular value decomposition
broadly applicable
average case
randomized algorithm
parallel algorithm
upper bound
active learning
search algorithm