A 1/2 approximation algorithm for energy-constrained geometric coverage problem

DOI10.1007/978-981-19-8152-4_7MaRDI QIDQ6535282zbMATH OpenFDO

Authors Huan Lan

Publication date 2 December 2023

Full work available at URL https://doi.org/10.1007/978-981-19-8152-4_7

zbMATH Keywords

energy-constraintgeometric coverage problemsgreedy algorithm

Mathematics Subject Classification ID

Wireless sensor networks as related to computer science (68M18) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• Energy-constrained geometric coverage problem
• An approximation algorithm for general energy restricted sweep coverage problem
• New approximations for maximum lifetime coverage
• Energy Efficient Monitoring in Sensor Networks

Cites work

• A note on the minimum power partial cover problem on the plane
• A primal-dual algorithm for the minimum partial set multi-cover problem
• A primal-dual approximation algorithm for the \(k\)-prize-collecting minimum power cover problem
• A PTAS for the disk cover problem of geometric objects
• A refined analysis of submodular greedy
• Algorithms for the line-constrained disk coverage and related problems
• Algorithms – ESA 2005
• Approximation algorithm for minimum power partial multi-coverage in wireless sensor networks
• Approximation algorithms for maximum coverage with group budget constraints
• Approximation algorithms for the minimum power cover problem with submodular/linear penalties
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Energy-constrained geometric coverage problem
• Maximising Real-Valued Submodular Functions: Primal and Dual Heuristics for Location Problems
• Maximum coverage problem with group budget constraints
• Minimum-cost coverage of point sets by disks
• Multi cover of a polygon minimizing the sum of areas
• Polynomial time approximation schemes for base station coverage with minimum total radii
• Practical budgeted submodular maximization
• The budgeted maximum coverage problem

Cited in

(1)

• Energy-constrained geometric coverage problem

This page was built for publication: A 1/2 approximation algorithm for energy-constrained geometric coverage problem

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