84 citations · 241 across the 22 of their papers we have counts for
4 papers · 1 filter
Improved approximation guarantees for weighted matching in the semi-streaming model
Leah Epstein, Asaf Levin, Julian Mestre +1
We study the maximum weight matching problem in the semi-streaming model, and improve on the currently best one-pass algorithm due to Zelke (Proc. of STACS2008, pages 669-680) by d…
Bin packing with general cost structures
Leah Epstein, Asaf Levin
Following the work of Anily et al., we consider a variant of bin packing, called "bin packing with general cost structures" (GCBP) and design an asymptotic fully polynomial time ap…
AFPTAS results for common variants of bin packing: A new method to handle the small items
Leah Epstein, Asaf Levin
We consider two well-known natural variants of bin packing, and show that these packing problems admit asymptotic fully polynomial time approximation schemes (AFPTAS). In bin packi…
Uniform unweighted set cover: The power of non-oblivious local search
Asaf Levin, Uri Yovel
We are given n base elements and a finite collection of subsets of them. The size of any subset varies between p to k (p < k). In addition, we assume that the input contains all po…