4 papers
Multicommodity Flows in Planar Graphs with Demands on Faces
Nikhil Kumar
We consider the problem of multicommodity flows in planar graphs. Seymour showed that if the union of supply and demand graphs is planar, then the cut condition is sufficient for r…
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…
Parallel Machine Scheduling to Minimize Energy Consumption
Antonios Antoniadis, Naveen Garg, Gunjan Kumar +1
Given n jobs with release dates, deadlines and processing times we consider the problem of scheduling them on m parallel machines so as to minimize the total energy consumed. Machi…
A Constant Factor Approximation for Capacitated Min-Max Tree Cover
Syamantak Das, Lavina Jain, Nikhil Kumar
Given a graph with non-negative real edge lengths and an integer parameter , the Min-Max k-Tree Cover problem seeks to find a set of at most subtrees of , such…