1.7k citations
- Technion – Israel Institute of TechnologyIL151 papers
- Oranim Academic College of EducationIL134 papers
- Tel Aviv UniversityIL55 papers
- Heidelberg UniversityDE36 papers
- Carmel (Israel)IL29 papers
- Columbia UniversityUS25 papers
- Massachusetts Institute of TechnologyUS25 papers
- National Research University Higher School of EconomicsRU25 papers
- University of AmsterdamNL22 papers
- Hebrew University of JerusalemIL21 papers
- Princeton UniversityUS21 papers
- Centre National de la Recherche ScientifiqueFR20 papers
4 papers · 2 filters
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…
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…
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…
On Approximating String Selection Problems with Outliers
Christina Boucher, Gad M. Landau, Avivit Levy +2
Many problems in bioinformatics are about finding strings that approximately represent a collection of given strings. We look at more general problems where some input strings can…