2 citations · 2 across the 6 of their papers we have counts for
7 papers
Approximate Max-Flow Min-Multicut Theorem for Graphs of Bounded Treewidth
Tobias Friedrich, Davis Issac, Nikhil Kumar +2
We prove an approximate max-multiflow min-multicut theorem for bounded treewidth graphs. In particular, we show the following: Given a treewidth- graph, there exists a (fraction…
An Approximate Generalization of the Okamura-Seymour Theorem
Nikhil Kumar
We consider the problem of multicommodity flows in planar graphs. Okamura and Seymour showed that if all the demands are incident on one face, then the cut-condition is sufficient…
Skeletons and Minimum Energy Scheduling
Antonios Antoniadis, Gunjan Kumar, Nikhil Kumar
Consider the problem where jobs, each with a release time, a deadline and a required processing time are to be feasibly scheduled in a single- or multi-processor setting so as…
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…