A Simple Distributed Algorithm for Sparse Fractional Covering and Packing Problems

2024/09/24 by Li, Qian, Ouyang, Minghui, Wang, Yuyi · 1 citation
#Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)

paper · doi:10.48550/arxiv.2409.16168

Abstract

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 ε.

Cited by

• Near-optimal streaming approximation for Max-DICUT in sublinear space using two passes

Related

• Algorithms to Approximate Column-Sparse Packing Problems
• The Complexity of Distributed Approximation of Packing and Covering Integer Linear Programs
• Solving Packing and Covering LPs in O((1)/(ε²)) Distributed Iterations with a Single Algorithm and Simpler Analysis
• A Deterministic Distributed 2-Approximation for Weighted Vertex Cover in O(log nlogΔ/ log²logΔ) Rounds
• Finding Sparse Solutions for Packing and Covering Semidefinite Programs