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

DOI10.1287/IJOC.2022.1201MaRDI QIDQ5058008zbMATH OpenOpenAlexWikidataFDO

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

zbMATH Keywords

\(p\)-percent coverconstant approximationlifetime scheduling

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Recommendations

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

Cites work

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

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)