245 citations · 596 across the 23 of their papers we have counts for
4 papers · 1 filter
Scheduling Distributed Clusters of Parallel Machines: Primal-Dual and LP-based Approximation Algorithms [Full Version]
Riley Murray, Samir Khuller, Megan Chao
The Map-Reduce computing framework rose to prominence with datasets of such size that dozens of machines on a single cluster were needed for individual jobs. As datasets approach t…
LP Rounding and Combinatorial Algorithms for Minimizing Active and Busy Time
Jessica Chang, Samir Khuller, Koyel Mukherjee
We consider fundamental scheduling problems motivated by energy issues. In this framework, we are given a set of jobs, each with a release time, deadline and required processing le…
Minimizing Uncertainty through Sensor Placement with Angle Constraints
Ioana O. Bercea, Volkan Isler, Samir Khuller
We study the problem of sensor placement in environments in which localization is a necessity, such as ad-hoc wireless sensor networks that allow the placement of a few anchors tha…
Constant factor Approximation Algorithms for Uniform Hard Capacitated Facility Location Problems: Natural LP is not too bad
Sapna Grover, Neelima Gupta, Samir Khuller +1
In this paper, we give first constant factor approximation for capacitated knapsack median problem (CKM) for hard uniform capacities, violating the budget only by an additive facto…