28 citations · 73 across the 23 of their papers we have counts for
Showing 2009Show all
2 papers · 1 filter
cs.CC2009★ 5 cited
On the Optimality of a Class of LP-based Algorithms
Amit Kumar, Rajsekar Manokaran, Madhur Tulsiani +1
In this paper we will be concerned with a class of packing and covering problems which includes Vertex Cover and Independent Set. Typically, one can write an LP relaxation and then…
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…