Constant Approximation for the Lifetime Scheduling Problem of p-Percent Coverage

DOI10.1287/ijoc.2022.1201zbMath1502.90081OpenAlexW4281480108WikidataQ114058181 ScholiaQ114058181MaRDI QIDQ5058008

Hongmin W. Du, Wei Liang, Zhao Zhang, Si-Wen 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

zbMATH Keywords

constant approximation\(p\)-percent coverlifetime scheduling

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Cites Work

• An approximation algorithm for maximum weight budgeted connected set cover
• Improved performance of the greedy algorithm for partial cover
• New approximations for minimum-weighted dominating sets and minimum-weighted connected dominating sets on unit disk graphs
• A unified approach to approximating partial covering problems
• Design and analysis of approximation algorithms
• A \(5+\varepsilon\)-approximation algorithm for minimum weighted dominating set in unit disk graph
• A better constant-factor approximation for weighted dominating set in unit disk graph
• Approximation algorithm for the partial set multi-cover problem
• Approximation algorithm for minimum power partial multi-coverage in wireless sensor networks
• Maximum lifetime connected coverage with two active-phase sensors
• Using Homogeneous Weights for Approximating the Partial Cover Problem
• Fast Approximation Algorithm for Maximum Lifetime Aggregation Trees in Wireless Sensor Networks
• (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
• Approximation algorithms for partial covering problems
• Breaking ther_maxBarrier: Enhanced Approximation Algorithms for Partial Set Multicover Problem
• Optimal Coverage in Wireless Sensor Networks
• Computing Minimum k-Connected m-Fold Dominating Set in General Graphs
• Breaking the O(ln n) Barrier: An Enhanced Approximation Algorithm for Fault-Tolerant Minimum Weight Connected Dominating Set
• New approximations for Maximum Lifetime Coverage
• Column generation algorithm for sensor coverage scheduling under bandwidth constraints

This page was built for publication: Constant Approximation for the Lifetime Scheduling Problem of p-Percent Coverage