Beep-and-sleep: message and energy efficient set cover

DOI10.1016/j.tcs.2023.113756OpenAlexW3188908868MaRDI QIDQ5925658

Christian Scheideler, Julian Werthmann, Thorsten Götte, Christina Kolb

Publication date: 17 March 2023

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2023.113756

zbMATH Keywords

approximation algorithmsset coverbeeping model\(K T_0\) model

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Distributed systems (68M14) Approximation algorithms (68W25) Distributed algorithms (68W15)

Cites Work

• Construction and Impromptu Repair of an MST in a Distributed Network with o(m) Communication
• The price of being near-sighted
• Deploying Wireless Networks with Beeps
• Distributed Computing: A Locality-Sensitive Approach
• On the complexity of local distributed graph problems
• Tight Bounds for Single-Pass Streaming Complexity of the Set Cover Problem
• Fractional Set Cover in the Streaming Model.
• An efficient distributed algorithm for constructing small dominating sets
• Improved Local Computation Algorithm for Set Cover via Sparsification
• Constant-time distributed dominating set approximation
• Fully Distributed Algorithms for Convex Optimization Problems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Beep-and-sleep: message and energy efficient set cover