24 citations · 25 across the 4 of their papers we have counts for
7 papers · 1 filter
Stochastic Load Balancing with Machine Reservations
David Alemán Espinosa, Naveen Garg, Sharat Ibrahimpur +2
We introduce a novel variant of stochastic load balancing that enables a quantitative tradeoff between the practical benefits of non-adaptive policies and their performance limitat…
Dual Half-integrality for Uncrossable Cut Cover and its Application to Maximum Half-Integral Flow
Naveen Garg, Nikhil Kumar
Given an edge weighted graph and a forest , the is to pick a minimum weighted set of edges, , such that every connected c…
Integer Plane Multiflow Maximisation : Flow-Cut Gap and One-Quarter-Approximation
Naveen Garg, Nikhil Kumar, András Sebő
In this paper, we bound the integrality gap and the approximation ratio for maximum plane multiflow problems and deduce bounds on the flow-cut-gap. Planarity means here that the un…
Non-clairvoyant Precedence Constrained Scheduling
Naveen Garg, Anupam Gupta, Amit Kumar +1
We consider the online problem of scheduling jobs on identical machines, where jobs have precedence constraints. We are interested in the demanding setting where the jobs sizes are…
On Fair Division of Indivisible Items
Bhaskar Chaudhury, Yun Kuen Cheung, Jugal Garg +3
We consider the task of assigning indivisible goods to a set of agents in a fair manner. Our notion of fairness is Nash social welfare, i.e., the goal is to maximize the geometric…
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…