Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2411.16578 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
Tabla de Contenidos:
- 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.