Search Results

Documents authored by Jain, Lavina


Document
APPROX
A Constant Factor Approximation for Capacitated Min-Max Tree Cover

Authors: Syamantak Das, Lavina Jain, and Nikhil Kumar

Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)


Abstract
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 (λ) 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λ [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 λ 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.

Cite as

Syamantak Das, Lavina Jain, and Nikhil Kumar. A Constant Factor Approximation for Capacitated Min-Max Tree Cover. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 55:1-55:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{das_et_al:LIPIcs.APPROX/RANDOM.2020.55,
  author =	{Das, Syamantak and Jain, Lavina and Kumar, Nikhil},
  title =	{{A Constant Factor Approximation for Capacitated Min-Max Tree Cover}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
  pages =	{55:1--55:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-164-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{176},
  editor =	{Byrka, Jaros{\l}aw and Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.55},
  URN =		{urn:nbn:de:0030-drops-126581},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2020.55},
  annote =	{Keywords: Approximation Algorithms, Graph Algorithms, Min-Max Tree Cover, Vehicle Routing, Steiner Tree}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail