DROPS

Document

DOI: 10.4230/LIPIcs.SWAT.2024.39

A Fast 3-Approximation for the Capacitated Tree Cover Problem with Edge Loads

Authors: Benjamin Rockel-Wolff

Published in: LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)

Abstract

The capacitated tree cover problem with edge loads is a variant of the tree cover problem, where we are given facility opening costs, edge costs and loads, as well as vertex loads. We try to find a tree cover of minimum cost such that the total edge and vertex load of each tree does not exceed a given bound. We present an 𝒪(mlog n) time 3-approximation algorithm for this problem. This is achieved by starting with a certain LP formulation. We give a combinatorial algorithm that solves the LP optimally in time 𝒪(mlog n). Then, we show that a linear time rounding and splitting technique leads to an integral solution that costs at most 3 times as much as the LP solution. Finally, we prove that the integrality gap of the LP is 3, which shows that we can not improve the rounding step in general.

Cite as

Benjamin Rockel-Wolff. A Fast 3-Approximation for the Capacitated Tree Cover Problem with Edge Loads. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 294, pp. 39:1-39:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{rockelwolff:LIPIcs.SWAT.2024.39,
  author =	{Rockel-Wolff, Benjamin},
  title =	{{A Fast 3-Approximation for the Capacitated Tree Cover Problem with Edge Loads}},
  booktitle =	{19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)},
  pages =	{39:1--39:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-318-8},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{294},
  editor =	{Bodlaender, Hans L.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.39},
  URN =		{urn:nbn:de:0030-drops-200793},
  doi =		{10.4230/LIPIcs.SWAT.2024.39},
  annote =	{Keywords: Approximation Algorithms, Tree Cover, LP}
}

Search Results

Documents authored by Rockel-Wolff, Benjamin

A Fast 3-Approximation for the Capacitated Tree Cover Problem with Edge Loads

Abstract

Cite as

Thanks for your feedback!

Could not send message