84 citations · 126 across the 21 of their papers we have counts for
Showing 2009Show all
2 papers · 1 filter
cs.DS2009★ 84 cited
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…
cs.DS2009★ 17 cited
Scheduling with Outliers
Anupam Gupta, Ravishankar Krishnaswamy, Amit Kumar +1
In classical scheduling problems, we are given jobs and machines, and have to schedule all the jobs to minimize some objective function. What if each job has a specified profit, an…