A Simple Distributed Algorithm for Sparse Fractional Covering and Packing Problems
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_ | 1866913515707564032 |
|---|---|
| author | Li, Qian Ouyang, Minghui Wang, Yuyi |
| author_facet | Li, Qian Ouyang, Minghui Wang, Yuyi |
| contents | This paper presents a distributed algorithm in the CONGEST model that achieves a $(1+ε)$-approximation for row-sparse fractional covering problems (RS-FCP) and the dual column-sparse fraction packing problems (CS-FPP). Compared with the best-known $(1+ε)$-approximation CONGEST algorithm for RS-FCP/CS-FPP developed by Kuhn, Moscibroda, and Wattenhofer (SODA'06), our algorithm is not only much simpler but also significantly improves the dependency on $ε$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_16168 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Simple Distributed Algorithm for Sparse Fractional Covering and Packing Problems Li, Qian Ouyang, Minghui Wang, Yuyi Data Structures and Algorithms Distributed, Parallel, and Cluster Computing This paper presents a distributed algorithm in the CONGEST model that achieves a $(1+ε)$-approximation for row-sparse fractional covering problems (RS-FCP) and the dual column-sparse fraction packing problems (CS-FPP). Compared with the best-known $(1+ε)$-approximation CONGEST algorithm for RS-FCP/CS-FPP developed by Kuhn, Moscibroda, and Wattenhofer (SODA'06), our algorithm is not only much simpler but also significantly improves the dependency on $ε$. |
| title | A Simple Distributed Algorithm for Sparse Fractional Covering and Packing Problems |
| topic | Data Structures and Algorithms Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2409.16168 |