39 citations · 308 across the 129 of their papers we have counts for
4 papers · 1 filter
Approximation Algorithms for Geometric Maximum Coverage
Sujoy Bhore, Timothy M. Chan, Pasin Manurangsi
We study the maximum coverage problem for geometric set systems: given a set of points, a set of geometric objects, and a number , select objects maximizing the number of po…
Computational Hardness of Private Coreset
Badih Ghazi, Cristóbal Guzmán, Pritish Kamath +3
We study the problem of differentially private (DP) computation of coreset for the -means objective. For a given input set of points, a coreset is another set of points such tha…
On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic
Karthik C. S., Pasin Manurangsi
Given a set of points in , the (monochromatic) Closest Pair problem asks to find a pair of distinct points in the set that are closest in the -metric. Clos…
Dissection with the Fewest Pieces is Hard, Even to Approximate
Jeffrey Bosboom, Erik D. Demaine, Martin L. Demaine +4
We prove that it is NP-hard to dissect one simple orthogonal polygon into another using a given number of pieces, as is approximating the fewest pieces to within a factor of $1+1/1…