Das, Syamantak; Jain, Lavina; Kumar, Nikhil A Constant Factor Approximation for Capacitated Min-Max Tree CoverApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM) 2020: 55:1–55:13
Given a graph \(G=(V,E)\) with non-negative real edge lengths and an integer parameter \(k\), the (uncapacitated) Min-Max Tree Cover problem seeks to find a set of at most \(k\) trees which together span \(V\) and each tree is a subgraph of \(G\). The objective is to minimize the maximum length among all the trees. In this paper, we consider a capacitated generalization of the above and give the first constant factor approximation algorithm. In the capacitated version, there is a hard uniform capacity (\(\lambda\)) on the number of vertices a tree can cover. Our result extends to the rooted version of the problem, where we are given a set of \(k\) root vertices, \(R\) and each of the covering trees is required to include a distinct vertex in \(R\) as the root. Prior to our work, the only result known was a \((2k-1)\)-approximation algorithm for the special case when the total number of vertices in the graph is \(k\lambda\) [Guttmann-Beck and Hassin, J. of Algorithms, 1997]. Our technique circumvents the difficulty of using the minimum spanning tree of the graph as a lower bound, which is standard for the uncapacitated version of the problem [Even et al., OR Letters 2004],[Khani et al., Algorithmica 2010]. Instead, we use Steiner trees that cover \(\lambda\) vertices along with an iterative refinement procedure that ensures that the output trees have low cost and the vertices are well distributed among the trees.
Garg, Naveen; Kumar, Nikhil Dual Half-Integrality for Uncrossable Cut Cover and Its Application to Maximum Half-Integral FlowEuropean Symposium on Algorithms (ESA) 2020: 55:1–55:13
Given an edge weighted graph and a forest \(F\), the {\em 2-edge connectivity augmentation problem} is to pick a minimum weighted set of edges, \(E'\), such that every connected component of \(E'\cup F\) is 2-edge connected. Williamson et al. gave a 2-approximation algorithm (WGMV) for this problem using the primal-dual schema. We show that when edge weights are integral, the WGMV procedure can be modified to obtain a half-integral dual. The 2-edge connectivity augmentation problem has an interesting connection to routing flow in graphs where the union of supply and demand is planar. The half-integrality of the dual leads to a tight 2-approximate max-half-integral-flow min-multicut theorem.
Garg, Naveen; Kumar, Nikhil; Sebö, András Integer Plane Multiflow Maximisation: Flow-Cut Gap and One-Quarter-ApproximationInteger Programming and Combinatorial Optimization (IPCO) 2020: 144–157
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. We consider instances where the union of the supply and demand graphs is planar and prove that there exists a multiflow of value at least half the capacity of a minimum multicut. We then show how to convert any multiflow into a half-integer flow of value at least half the original multiflow. Finally, we round any half-integer multiflow into an integer multiflow, losing at most half the value thus providing a 1/4-approximation algorithm and integrality gap for maximum integer multiflows in the plane.
Kumar, Nikhil Multicommodity Flows in Planar Graphs with Demands on FacesInternational Symposium on Algorithms and Computation (ISAAC) 2020: 1–11
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 also sufficient for routing demands. Okamura-Seymour showed that if the supply graph is planar and all demands are incident on one face, then again the cut condition is sufficient for routing demands. We consider a common generalization of these settings where the end points of each demand are on the same face of the planar graph. We show that if the source sink pairs on each face of the graph are such that sources and sinks appear contiguously on the cycle bounding the face, then the flow cut gap is at most 3. We come up with a notion of approximating demands on a face by convex combination of laminar demands to prove this result.
Antoniadis, Antonios; Garg, Naveen; Kumar, Gunjan; Kumar, Nikhil Parallel Machine Scheduling to Minimize Energy ConsumptionSymposium on Discrete Algorithms (SODA) 2020: 2758–2769
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. Machines can enter a sleep state and they consume no energy in this state. Each machine requires \(L\) units of energy to awaken from the sleep state and in its active state the machine can process jobs and consumes a unit of energy per unit time. We allow for preemption and migration of jobs and provide the first constant approximation algorithm for this problem.
