Forest Covers and Bounded Forest Covers
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912132482727936 |
|---|---|
| author | Gaur, Daya Ram Gorain, Barun Patra, Shaswati Singh, Rishi Ranjan |
| author_facet | Gaur, Daya Ram Gorain, Barun Patra, Shaswati Singh, Rishi Ranjan |
| contents | We study approximation algorithms for the forest cover and bounded forest cover problems. A probabilistic $2+ε$ 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+ε$ approximation algorithm may be of independent interest. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_16578 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Forest Covers and Bounded Forest Covers Gaur, Daya Ram Gorain, Barun Patra, Shaswati Singh, Rishi Ranjan Data Structures and Algorithms Computational Complexity Combinatorics We study approximation algorithms for the forest cover and bounded forest cover problems. A probabilistic $2+ε$ 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+ε$ approximation algorithm may be of independent interest. |
| title | Forest Covers and Bounded Forest Covers |
| topic | Data Structures and Algorithms Computational Complexity Combinatorics |
| url | https://arxiv.org/abs/2411.16578 |