A PTAS for the budgeted power maximum coverage problem

DOI10.1016/J.TCS.2025.115606MaRDI QIDQ6888784zbMATH OpenFDO

Authors Yuxuan Xu, Yingli Ran

Publication date 5 December 2025

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.TCS.2025.115606

zbMATH Keywords

approximation algorithmbudgeted powermaximum coveragePTAS

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)

Cites work

• A note on multicovering with disks
• 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 partial cover problem
• Approximation and Online Algorithms
• Approximation schemes for covering and packing problems in image processing and VLSI
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Bicriteria approximation algorithms for the unit disk coverage problem
• Clustering to minimize the sum of cluster diameters
• Fault-tolerant covering problems in metric spaces
• scientific article; zbMATH DE number 7788391 (Why is no real title available?)
• Minimum power partial multi-cover on a line
• Minimum-cost coverage of point sets by disks
• Polynomial time approximation schemes for base station coverage with minimum total radii
• Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
• PTAS for minimum cost multicovering with disks
• Unit disk graphs

This page was built for publication: A PTAS for the budgeted power maximum coverage problem

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