A simple distributed algorithm for sparse fractional covering and packing problems

DOI10.4230/LIPICS.ISAAC.2024.45MaRDI QIDQ7260665zbMATH OpenFDO

Authors Minghui Ouyang, Yuyi Wang, Qian Li

Publication date 8 June 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ISAAC.2024.45

zbMATH Keywords

column-sparse fractional packingCONGEST modelpositive linear programmingrow-sparse fractional coveringsimple algorithms

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites work

• Constant-time distributed dominating set approximation
• Distributed approximate maximum matching in the CONGEST model
• Global optimization using local information with applications to flow control
• scientific article; zbMATH DE number 2079379 (Why is no real title available?)
• Linear programming without the matrix
• Local computation: lower and upper bounds
• Minimum dominating set approximation in graphs of bounded arboricity
• Stateless distributed gradient descent for positive linear programs
• Survey of local algorithms
• The price of being near-sighted
• What cannot be computed locally!

This page was built for publication: A simple distributed algorithm for sparse fractional covering and packing problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7260665)