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

DOI10.1007/978-981-19-8152-4_6zbMATH Open1541.68442MaRDI QIDQ6535281FDOQ6535281

Authors: Han Dai 

Publication date: 2 December 2023

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

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)

Cites Work

• An analysis of the greedy algorithm for the submodular set covering problem
• Approximation algorithms for the minimum power cover problem with submodular/linear penalties
• Approximation algorithm for minimum power partial multi-coverage in wireless sensor networks
• A primal-dual algorithm for the minimum partial set multi-cover problem
• Minimum power partial multi-cover on a line
• A primal-dual approximation algorithm for the \(k\)-prize-collecting minimum power cover problem
• A note on the minimum power partial cover problem on the plane
• Capacitated covering problems in geometric spaces
• Title not available (Why is that?)

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)