A Simple Distributed Algorithm for Sparse Fractional Covering and Packing Problems
<|reference_start|>A Simple Distributed Algorithm for Sparse Fractional Covering and Packing Problems: This paper presents a distributed algorithm in the CONGEST model that achieves a $(1+\epsilon)$-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+\epsilon)$-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 $\epsilon$.<|reference_end|>
@article{li2024a,
    title={A Simple Distributed Algorithm for Sparse Fractional Covering and
  Packing Problems},
    author={Qian Li, Minghui Ouyang, and Yuyi Wang},
    journal={arXiv preprint arXiv:2409.16168},
    year={2024},
    archivePrefix={arXiv},
    eprint={2409.16168},
    primaryClass={cs.DS cs.DC}
}