Forest Covers and Bounded Forest Covers
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _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 |