An approximation algorithm for the minimum soft capacitated disk multi-coverage problem

DOI10.1007/978-981-19-8152-4_6MaRDI QIDQ6535281zbMATHFDO

Authors Han Dai

Publication date 2 December 2023

zbMATH Keywords

approximation algorithmLP roundingsoft capacitymulti-coverage

Mathematics Subject Classification ID

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

Recommendations

• A constant-factor approximation for multi-covering with disks
• A note on multicovering with disks
• A constant-factor approximation for multi-covering with disks
• A note on the minimum power partial cover problem on the plane
• Approximation algorithms for the minimum power partial cover problem

Cites work

• scientific article; zbMATH DE number 7651148 (Why is no real title available?)
• 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
• An analysis of the greedy algorithm for the submodular set covering problem
• Approximation algorithm for minimum power partial multi-coverage in wireless sensor networks
• Approximation algorithms for the minimum power cover problem with submodular/linear penalties
• Capacitated covering problems in geometric spaces
• Minimum power partial multi-cover on a line

This page was built for publication: An approximation algorithm for the minimum soft capacitated disk multi-coverage problem

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