6 papers · 1 filter
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…
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…
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…