Fetching the paper…
Reading the bibliography…
Given a set $F$ of $n$ positive functions over a ground set $X$, we consider the problem of computing $x^*$ that minimizes the expression $\sum_{f\in F}f(x)$, over $x\in X$.
On the uniform convergence of relative frequencies of events to their probabilities
V. N. Vapnik and A. Y. Chervonenkis · 1971
Earlier work this paper cites.
Finding least-distance lines
N. Meggido and A. Tamir · 1983
Earlier work this paper cites.
Epsilon-nets and simplex range queries
D. Haussler and E. Welzl · 1986
Earlier work this paper cites.
A deterministic view of random sampling and its use in geometry
B. Chazelle and J. Friedman · 1990
Earlier work this paper cites.
Almost optimal set covers in finite VC-dimension
H. Brönnimann and M.T. Goodrich · 1995
Earlier work this paper cites.
Improved bounds on weak epsilon-nets for convex sets
Chazelle, Edelsbrunner, Grigni, Guibas, Sharir, and Welzl · 1995
Earlier work this paper cites.
Approximations and optimal geometric divide-and-conquer
J. Matoušek · 1995
Earlier work this paper cites.
Davenport-Schinzel Sequences and Their Geometric Applications
M. Sharir and P. K. Agarwal · 1995
Earlier work this paper cites.
Matrix Computations
Gene H. Golub and Charles F. Van Loan · 1996
Earlier work this paper cites.
Sublinear time algorithms for metric space problems
P. Indyk · 1999
Earlier work this paper cites.
Improved bounds on the sample complexity of learning
Yi Li, Philip M. Long, and Aravind Srinivasan · 2000
Earlier work this paper cites.
Algorithms for facility location problems with outliers
M. Charikar, S. Khuller, D. M. Mount, and G. Narasimhan · 2001
Earlier work this paper cites.
Improved bounds on the sample complexity of learning
Y. Li, P. M. Long, and A. Srinivasan · 2001
Earlier work this paper cites.
An elementary proof of a theorem of johnson and lindenstrauss
Sanjoy Dasgupta and Anupam Gupta · 2003
Earlier work this paper cites.
No coreset, no cry
S. Har-Peled · 2004
Earlier work this paper cites.
On coresets for k-means and k-median clustering
S. Har-Peled and S. Mazumdar · 2004
Earlier work this paper cites.
Optimal time bounds for approximate clustering
Mettu and Plaxton · 2004
Cited alongside, same era.
Geometric approximations via coresets
P. K. Agarwal, S. Har-Peled, and K. R. Varadarajan · 2005
Cited alongside, same era.
Subgradient and sampling algorithms for l 1 l_{1} -regression
K. L. Clarkson · 2005
Cited alongside, same era.
On k k -median clusteing in high dimensions
K. Chen · 2006
Cited alongside, same era.
Sampling algorithms for l 2 l_{2} regression and applications
P. Drineas, M. W. Mahoney, and S. Muthukrishnan · 2006
Cited alongside, same era.
Matrix approximation and projective clustering via volume sampling
A. Deshpande, L. Rademacher, S. Vempala, and G. Wang · 2006
Cited alongside, same era.
Efficient subspace approximation algorithms
N. D. Shyamalkumar and K. R. Varadarajan · 2007
Later among the works it cites.
A constant factor approximation algorithm for k -median clustering with outliers
K. Chen · 2008
Later among the works it cites.
Sampling algorithms and coresets for ℓ p \ell_{p} -regression
A. Dasgupta, P. Drineas, B. Harb, R. Kumar, and M. W. Mahoney · 2008
Later among the works it cites.
Twice-ramanujan sparsifiers
J.D. Batson, D.A. Spielman, and N. Srivastava · 2009
Later among the works it cites.
Numerical linear algebra in the streaming model
K. L. Clarkson and David P. Woodruff · 2009
Later among the works it cites.
Private coresets
D. Feldman, A. Fiat, H. Kaplan, and K. Nissim · 2009
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Coresets for weighted facilities and their applications
D. Feldman, A. Fiat, and M. Sharir · 2006
Cited alongside, same era.
Coresets for discrete integration and clustering
S. Har-Peled · 2006
Cited alongside, same era.
Improved approximation algorithms for large matrices via random projections
T. Sarlós · 2006
Cited alongside, same era.
Deterministic sampling and range counting in geometric data streams
A. Bagchi, A. Chaudhary, D. Eppstein, and M. T. Goodrich · 2007
Cited alongside, same era.
Sublinear-time approximation algorithms for clustering via random sampling
A. Czumaj and C. Sohler · 2007
Cited alongside, same era.
Sampling-based dimension reduction for subspace approximation
A. Deshpande and K. R. Varadarajan · 2007
Cited alongside, same era.
Geometric approximation algorithms. manuscript
S. Har-Peled · 2009
Later among the works it cites.
CUR matrix decompositions for improved data analysis
M.W. Mahoney and P. Drineas · 2009
Later among the works it cites.
Coresets and sketches for high dimensional subspace approximation problems
D. Feldman, M. Monemizadeh, C. Sohler, and D. P. Woodruff · 2010
Later among the works it cites.
Linear-time approximation schemes for clustering problems in any dimensions
Amit Kumar, Yogish Sabharwal, and Sandeep Sen · 2010
Later among the works it cites.
Universal ε \varepsilon approximators for integrals
M. Langberg and L. J. Schulman · 2010
Later among the works it cites.
Algorithms and hardness for subspace approximation
N.K. Vishnoi A. Deshpande, M. Tulsiani · 2011
Closest in time.
Near-optimal column-based matrix reconstruction, March 04 2011
C. Boutsidis, P. Drineas, and M. Magdon-Ismail · 2011
Closest in time.
From high definition image to low space optimization
M. Feigin, D. Feldman, and Nir Sochen · 2011
Closest in time.
Sparse quadratic forms and their geometric applications (after Batson, Spielman and Srivastava)
A. Naor · 2011
Closest in time.