3 papers
cs.DS2020
Improved Approximations for Min Sum Vertex Cover and Generalized Min Sum Set Cover
Nikhil Bansal, Jatin Batra, Majid Farhadi +1
We study the generalized min sum set cover (GMSSC) problem, wherein given a collection of hyperedges with arbitrary covering requirements , the goal is to find an ordering…
cs.DS2019
Non-uniform Geometric Set Cover and Scheduling on Multiple Machines
Nikhil Bansal, Jatin Batra
We consider the following general scheduling problem studied recently by Moseley. There are jobs, all released at time , where job has size and an associated arbit…
cs.DS2018
Constant Factor Approximation Algorithm for Weighted Flow Time on a Single Machine in Pseudo-polynomial time
Jatin Batra, Naveen Garg, Amit Kumar
In the weighted flow-time problem on a single machine, we are given a set of n jobs, where each job has a processing requirement p_j, release date r_j and weight w_j. The goal is t…