Autor:	Gaur, Daya Ram, Gorain, Barun, Patra, Shaswati, Singh, Rishi Ranjan
Rok vydání:	2024
Předmět:	Computer Science - Data Structures and Algorithms Computer Science - Computational Complexity Mathematics - Combinatorics
Druh dokumentu:	Working Paper
Popis:	We study approximation algorithms for the forest cover and bounded forest cover problems. A probabilistic $2+\epsilon$ approximation algorithm for the forest cover problem is given using the method of dual fitting. A deterministic algorithm with a 2-approximation ratio that rounds the optimal solution to a linear program is given next. The 2-approximation for the forest cover is then used to give a 6-approximation for the bounded forest cover problem. The use of the probabilistic method to develop the $2+\epsilon$ approximation algorithm may be of independent interest.
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2411.16578 Zobrazit plný text záznamu View this record from Arxiv