Fetching the paper…
Reading the bibliography…
Consider the following problem: given a metric space, some of whose points are "clients", open a set of at most $k$ facilities to minimize the average distance from the clients to these facilities.
Maximal flow through a network
L.R. Ford and D.R. Fulkerson · 1956
Earlier work this paper cites.
Approximation algorithms for combinatorial problems
D.S. Johnson · 1974
Earlier work this paper cites.
An analysis of approximations for maximizing submodular set functions—I
GL Nemhauser, LA Wolsey, and ML Fisher · 1978
Earlier work this paper cites.
A greedy heuristic for the set-covering problem
V. Chvátal · 1979
Earlier work this paper cites.
Approximation algorithms for the set covering and vertex cover problems
D.S. Hochbaum · 1982
Earlier work this paper cites.
A simple probabilistic approximation algorithm for vertex cover
L. Pitt · 1985
Earlier work this paper cites.
Global min-cuts in RNC, and other ramifications of a simple min-cut algorithm
David R. Karger · 1993
Earlier work this paper cites.
Private approximation of NP-hard functions
S. Halevi, R. Krauthgamer, E. Kushilevitz, and K. Nissim · 2001
Earlier work this paper cites.
Local search heuristics for k k -median and facility location problems
Vijay Arya, Naveen Garg, Rohit Khandekar, Adam Meyerson, Kamesh Munagala, and Vinayaka Pandit · 2004
Earlier work this paper cites.
A tight bound on approximating arbitrary metrics by tree metrics
Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar · 2004
Earlier work this paper cites.
Algorithms for dynamic geometric problems over data streams
P. Indyk · 2004
Cited alongside, same era.
Private approximation of search problems
A. Beimel, P. Carmi, K. Nissim, and E. Weinreb · 2006
Cited alongside, same era.
Our data, ourselves: privacy via distributed noise generation
Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor · 2006
Cited alongside, same era.
Calibrating noise to sensitivity in private data analysis
C. Dwork, F. McSherry, K. Nissim, and A. Smith · 2006
Cited alongside, same era.
Differential privacy
Cynthia Dwork · 2006
Cited alongside, same era.
Secure multiparty computation of approximations
Joan Feigenbaum, Yuval Ishai, Tal Malkin, Kobbi Nissim, Martin J. Strauss, and Rebecca N. Wright · 2006
Cited alongside, same era.
Smooth sensitivity and sampling in private data analysis
Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith · 2007
Later among the works it cites.
A learning theory approach to non-interactive database privacy
A. Blum, K. Ligett, and A. Roth · 2008
Later among the works it cites.
Distributed private data analysis: Simultaneously solving how and what
Amos Beimel, Kobbi Nissim, and Eran Omri · 2008
Later among the works it cites.
Differential Privacy: A Survey of Results
C. Dwork · 2008
Later among the works it cites.
What can we learn privately?
Shiva Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith · 2008
Later among the works it cites.
Privacy: Theory meets practice on the map
Ashwin Machanavajjhala, Daniel Kifer, John M. Abowd, Johannes Gehrke, and Lars Vilhuber · 2008
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Polylogarithmic Private Approximations and Efficient Matching
P. Indyk and D. Woodruff · 2006
Cited alongside, same era.
Private Approximation of Clustering and Vertex Cover
A. Beimel, R. Hallak, and K. Nissim · 2007
Cited alongside, same era.
How Should We Solve Search Problems Privately?
A. Beimel, T. Malkin, K. Nissim, and E. Weinreb · 2007
Cited alongside, same era.
Mechanism Design via Differential Privacy
F. McSherry and K. Talwar · 2007
Cited alongside, same era.
On the Hardness of Being Truthful
C. Papadimitriou, M. Schapira, and Y. Singer · 2008
Later among the works it cites.
On the complexity of differentially private data release: efficient algorithms and hardness results
C. Dwork, M. Naor, O. Reingold, G.N. Rothblum, and S. Vadhan · 2009
Closest in time.
Private coresets
D. Feldman, A. Fiat, H. Kaplan, and K. Nissim · 2009
Closest in time.