Minimum power partial multi-cover on a line

DOI10.1016/J.TCS.2021.02.033MaRDI QIDQ2661770zbMATH OpenOpenAlexFDO

Authors Wei Liang, Menghong Li, Zhao Zhang, Xiaohui Huang

Publication date 8 April 2021

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

Full work available at URL https://doi.org/10.1016/j.tcs.2021.02.033

zbMATH Keywords

dynamic programminglinear programmingpartial multi-covertotally unimodular

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Discrete location and assignment (90B80) Linear programming (90C05) Dynamic programming (90C39)

Recommendations

• Min-Power Covering Problems
• A note on the minimum power partial cover problem on the plane
• A primal-dual algorithm for the minimum power partial cover problem
• On minimum power connectivity problems
• On Minimum Power Connectivity Problems
• Approximation algorithm for minimum power partial multi-coverage in wireless sensor networks
• Improved approximation algorithms for minimum power covering problems
• Improved approximation algorithms for minimum power covering problems

Cites work

• A bicriteria algorithm for the minimum submodular cost partial set multi-cover problem
• A constant-factor approximation for multi-covering with disks
• A constant-factor approximation for multi-covering with disks
• A new polynomial-time algorithm for linear programming
• A note on multicovering with disks
• A primal-dual algorithm for the minimum partial set multi-cover problem
• Algorithms – ESA 2005
• Approximation algorithms for partial covering problems
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• Approximation and Online Algorithms
• scientific article; zbMATH DE number 3121293 (Why is no real title available?)
• Improved results on geometric hitting set problems
• Integral Extreme Points
• Multi cover of a polygon minimizing the sum of areas
• On partial covering for geometric set systems
• Packing and covering with non-piercing regions
• Quasi-Polynomial Time Approximation Scheme for Weighted Geometric Set Cover on Pseudodisks and Halfspaces
• Set covering with almost consecutive ones property
• Solving tall dense linear programs in nearly linear time
• Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling
• Weighted geometric set cover via quasi-uniform sampling
• Weighted geometric set multi-cover via quasi-uniform sampling

Cited in

(17)

• Approximation algorithm for minimum power partial multi-coverage in wireless sensor networks
• A primal-dual approximation algorithm for the \(k\)-prize-collecting minimum power cover problem
• A primal-dual algorithm for the minimum power partial cover problem
• Constant-approximation for prize-collecting min-sensor sweep coverage with base stations
• A note on the minimum power partial cover problem on the plane
• Parallel approximation for partial set cover
• Approximation algorithms for the minimum power cover problem with submodular/linear penalties
• Minimum shared‐power edge cut
• The bound coverage problem by aligned disks in \(L_1\) metric
• An improved approximation algorithm for the k-prize-collecting minimum power cover problem
• An approximation algorithm for the H-prize-collecting power cover problem
• Approximation algorithms for the minimum power partial cover problem
• An approximation algorithm for the minimum soft capacitated disk multi-coverage problem
• The K-prize-collecting coverage problem by aligned disks
• A PTAS for the budgeted power maximum coverage problem
• The online power cover problem on a line
• Algorithms for the online power cover problem on a line

This page was built for publication: Minimum power partial multi-cover on a line

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