Constant approximation for the lifetime scheduling problem of p-percent coverage

DOI10.1287/IJOC.2022.1201zbMATH Open1502.90081OpenAlexW4281480108WikidataQ114058181 ScholiaQ114058181MaRDI QIDQ5058008FDOQ5058008

Authors: Zhao Zhang, Wei Liang, Hongmin W. Du, S. W. Liu 

Publication date: 1 December 2022

Published in: INFORMS Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/ijoc.2022.1201

Recommendations

• New approximations for maximum lifetime coverage
• scientific article; zbMATH DE number 1182760
• Approximation algorithms for the connected sensor cover problem
• The generalized maximum coverage problem
• On the p‐coverage problem on the real line

zbMATH Keywords

constant approximation\(p\)-percent coverlifetime scheduling

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Cites Work

• Using homogeneous weights for approximating the partial cover problem
• Approximation algorithms for partial covering problems
• An approximation algorithm for maximum weight budgeted connected set cover
• Improved performance of the greedy algorithm for partial cover
• Column generation algorithm for sensor coverage scheduling under bandwidth constraints
• A unified approach to approximating partial covering problems
• New approximations for minimum-weighted dominating sets and minimum-weighted connected dominating sets on unit disk graphs
• Design and analysis of approximation algorithms
• A \(5+\varepsilon\)-approximation algorithm for minimum weighted dominating set in unit disk graph
• Computing Minimum k-Connected m-Fold Dominating Set in General Graphs
• A better constant-factor approximation for weighted dominating set in unit disk graph
• A (4 + ε)-Approximation for the Minimum-Weight Dominating Set Problem in Unit Disk Graphs
• Approximation algorithm for the partial set multi-cover problem
• Maximum lifetime connected coverage with two active-phase sensors
• (6 + ε)-Approximation for Minimum Weight Dominating Set in Unit Disk Graphs
• Approximation algorithm for minimum power partial multi-coverage in wireless sensor networks
• Optimal coverage in wireless sensor networks
• Breaking ther_maxBarrier: Enhanced Approximation Algorithms for Partial Set Multicover Problem
• Breaking the O(ln n) Barrier: An Enhanced Approximation Algorithm for Fault-Tolerant Minimum Weight Connected Dominating Set
• Fast approximation algorithm for maximum lifetime aggregation trees in wireless sensor networks
• New approximations for maximum lifetime coverage

Cited In (1)

• New approximations for maximum lifetime coverage

This page was built for publication: Constant approximation for the lifetime scheduling problem of \(p\)-percent coverage

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