124 citations
- Indian Institute of Technology KharagpurIN5 papers
- Institut national de recherche en sciences et technologies du numériqueFR4 papers
- Google (United States)US2 papers
- Microsoft Research (United Kingdom)GB2 papers
- Microsoft (United States)US2 papers
- The Ohio State UniversityUS2 papers
- University of BolognaIT2 papers
- Carnegie Mellon UniversityUS1 paper
- Centre de Recherche en InformatiqueFR1 paper
- Etsy (United States)US1 paper
- Georgia Institute of TechnologyUS1 paper
- Hebrew University of JerusalemIL1 paper
Showing 2010Show all
3 papers · 1 filter
cs.DS2010★ 3 cited
Approximability of Capacitated Network Design
Deeparnab Chakrabarty, Chandra Chekuri, Sanjeev Khanna +1
In the {\em capacitated} survivable network design problem (Cap-SNDP), we are given an undirected multi-graph where each edge has a capacity and a cost. The goal is to find a minim…
cs.DS2010★ 10 cited
Efficient volume sampling for row/column subset selection
Amit Deshpande, Luis Rademacher
We give efficient algorithms for volume sampling, i.e., for picking -subsets of the rows of any given matrix with probabilities proportional to the squared volumes of the simpli…
cs.DS2010
Differential Privacy and the Fat-Shattering Dimension of Linear Queries
Aaron Roth
In this paper, we consider the task of answering linear queries under the constraint of differential privacy. This is a general and well-studied class of queries that captures othe…