Distributed fractional local ratio and independent set approximation

DOI10.1016/J.IC.2024.105238MaRDI QIDQ7021352zbMATH OpenFDO

Authors Magnús M. Halldórsson, Dror Rawitz

Publication date 28 February 2025

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.IC.2024.105238

zbMATH Keywords

approximation algorithmsdistributed algorithmsfractional local ratiomaximum weight independent set

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15) Approximation algorithms (68W25)

Cites work

• A deterministic distributed 2-approximation for weighted vertex cover in \(O(\log N\log\varDelta/\log^2\log\varDelta)\) rounds
• A Distributed (2 + ε)-Approximation for Vertex Cover in O(log Δ / ε log log Δ) Rounds
• A unified approach to approximating resource allocation and scheduling
• Admission control in networks with advance reservations
• Admission control with advance reservations in simple networks
• Approximation Resistance from Pairwise-Independent Subgroups
• Deterministic (+1)-coloring in sublinear (in ) time in static, dynamic, and faulty networks
• Distributed \((\Delta+1)\)-coloring in linear (in \(\Delta\)) time
• Distributed approximation of cellular coverage
• Distributed approximation of maximum independent set and maximum matching
• Distributed Symmetry Breaking on Power Graphs via Sparsification
• Efficient bounds for the stable set, vertex cover and set packing problems
• scientific article; zbMATH DE number 3889282 (Why is no real title available?)
• scientific article; zbMATH DE number 6865614 (Why is no real title available?)
• Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
• Improved distributed approximations for maximum independent set
• Local computation: lower and upper bounds
• Local distributed rounding: generalized to MIS, matching, set cover, and beyond
• On constant time approximation of parameters of bounded degree graphs
• On the complexity of local distributed graph problems
• On tree-constrained matchings and generalizations
• Optimization problems in multiple subtree graphs
• Quadratic and near-quadratic lower bounds for the CONGEST model
• Scheduling Split Intervals
• Simple and local independent set approximation
• The price of being near-sighted
• Using fractional primal-dual to schedule split intervals with demands

This page was built for publication: Distributed fractional local ratio and independent set approximation

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