24 citations · 40 across the 9 of their papers we have counts for
9 papers
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…
Rejecting Jobs to Minimize Load and Maximum Flow-time
Anamitra Roy Choudhury, Syamantak Das, Naveen Garg +1
Online algorithms are usually analyzed using the notion of competitive ratio which compares the solution obtained by the algorithm to that obtained by an online adversary for the w…
A 4/3-approximation for TSP on cubic 3-edge-connected graphs
Nishita Aggarwal, Naveen Garg, Swati Gupta
We provide a polynomial time 4/3 approximation algorithm for TSP on metrics arising from the metric completion of cubic 3-edge connected graphs.
On-Line End-to-End Congestion Control
Naveen Garg, Neal E. Young
Congestion control in the current Internet is accomplished mainly by TCP/IP. To understand the macroscopic network behavior that results from TCP/IP and similar end-to-end protocol…