84 citations · 241 across the 22 of their papers we have counts for
Showing 2012Show all
3 papers · 1 filter
cs.DS2012
A unified approach to truthful scheduling on related machines
Leah Epstein, Asaf Levin, Rob van Stee
We present a unified framework for designing deterministic monotone polynomial time approximation schemes (PTAS's) for a wide class of scheduling problems on uniformly related mach…
cs.DS2012★ 12 cited
Improved Bounds for Online Preemptive Matching
Leah Epstein, Asaf Levin, Danny Segev +1
When designing a preemptive online algorithm for the maximum matching problem, we wish to maintain a valid matching M while edges of the underlying graph are presented one after th…
cs.DS2012★ 1 cited
An efficient polynomial time approximation scheme for load balancing on uniformly related machines
Leah Epstein, Asaf Levin
We consider basic problems of non-preemptive scheduling on uniformly related machines. For a given schedule, defined by a partition of the jobs into m subsets corresponding to the…