Constant-approximation for minimum weight partial sensor cover

DOI10.1142/S1793830921500476OpenAlexW3095724878MaRDI QIDQ5013505

Hongmin W. Du, Si-Wen Liu

Publication date: 30 November 2021

Published in: Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s1793830921500476

zbMATH Keywords

constant-approximation algorithmdynamic program techniqueminimum weight sensor coverpartial sensor cover

Mathematics Subject Classification ID

Approximation algorithms (68W25)

Cites Work

• New approximations for minimum-weighted dominating sets and minimum-weighted connected dominating sets on unit disk graphs
• A \(5+\varepsilon\)-approximation algorithm for minimum weighted dominating set in unit disk graph
• A PTAS for the Weighted Unit Disk Cover Problem
• (6 + ε)-Approximation for Minimum Weight Dominating Set in Unit Disk Graphs
• A (4 + ε)-Approximation for the Minimum-Weight Dominating Set Problem in Unit Disk Graphs
• Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs
• Approximation algorithms for partial covering problems
• New approximations for Maximum Lifetime Coverage

This page was built for publication: Constant-approximation for minimum weight partial sensor cover