Minimum power partial multi-cover on a line

DOI10.1016/j.tcs.2021.02.033zbMath1501.90044OpenAlexW3130744364MaRDI QIDQ2661770

Zhao Zhang, Menghong Li, Wei Liang, Xiao-hui 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

linear programmingdynamic programmingtotally unimodularpartial multi-cover

Mathematics Subject Classification ID

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

Related Items

Constant-approximation for prize-collecting min-sensor sweep coverage with base stations ⋮ A note on the minimum power partial cover problem on the plane ⋮ Approximation algorithms for the minimum power cover problem with submodular/linear penalties ⋮ 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 ⋮ Parallel approximation for partial set cover ⋮ Approximation algorithm for minimum power partial multi-coverage in wireless sensor networks

Cites Work

• Unnamed Item
• Unnamed Item
• Improved results on geometric hitting set problems
• A new polynomial-time algorithm for linear programming
• A note on multicovering with disks
• Packing and covering with non-piercing regions
• A bicriteria algorithm for the minimum submodular cost partial set multi-cover problem
• A primal-dual algorithm for the minimum partial set multi-cover problem
• Set covering with almost consecutive ones property
• Weighted geometric set cover via quasi-uniform sampling
• Weighted Geometric Set Multi-cover via Quasi-uniform Sampling
• A constant-factor approximation for multi-covering with disks
• Multi Cover of a Polygon Minimizing the Sum of Areas
• Quasi-Polynomial Time Approximation Scheme for Weighted Geometric Set Cover on Pseudodisks and Halfspaces
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• Approximation algorithms for partial covering problems
• On Partial Covering For Geometric Set Systems
• Solving tall dense linear programs in nearly linear time
• A constant-factor approximation for multi-covering with disks
• Algorithms – ESA 2005
• Integral Extreme Points
• Approximation and Online Algorithms