Approximation algorithm for minimum partial multi-cover under a geometric setting

DOI10.1007/S11590-021-01746-9MaRDI QIDQ2115321zbMATH OpenOpenAlexFDO

Authors Yingli Ran, Zhao Zhang, Du Ding-Zhu, Xiaohui Huang

Publication date 15 March 2022

Published in Optimization Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s11590-021-01746-9

zbMATH Keywords

approximation algorithmunit squarepartial set multi-cover

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Recommendations

• On the set multi-cover problem in geometric settings
• On the set multicover problem in geometric settings
• On partial covering for geometric set systems
• On the geometric set multicover problem
• Approximation algorithm for the partial set multi-cover problem

Cites work

• scientific article; zbMATH DE number 1839431 (Why is no real title available?)
• 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
• Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph
• Approximation algorithm for partial positive influence problem in social network
• Approximation algorithm for the partial set multi-cover problem
• Approximation algorithms for partial covering problems
• Approximation schemes for covering and packing problems in image processing and VLSI
• Breaking ther_maxBarrier: Enhanced Approximation Algorithms for Partial Set Multicover Problem
• Geometric approximation algorithms
• Geometric red-blue set cover for unit squares and related problems
• Local ratio method on partial set multi-cover
• Minimizing the union: tight approximations for small set bipartite vertex expansion
• On partial covering for geometric set systems
• On positive influence dominating sets in social networks
• On the set multicover problem in geometric settings
• Positive Influence Dominating Set in Online Social Networks
• The densest \(k\)-subhypergraph problem
• Using homogeneous weights for approximating the partial cover problem
• Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling
• Weighted geometric set multi-cover via quasi-uniform sampling

Cited in

(9)

• On the set multicover problem in geometric settings
• Improved approximation algorithms for geometric set cover
• A primal-dual algorithm for the minimum partial set multi-cover problem
• Linear Time Approximation Schemes for Geometric Maximum Coverage
• On partial covering for geometric set systems
• On the set multi-cover problem in geometric settings
• Minimum-membership geometric set cover, revisited
• On the geometric set multicover problem
• A bicriteria approximation algorithm for minimum submodular cost partial multi-cover problem

This page was built for publication: Approximation algorithm for minimum partial multi-cover under a geometric setting

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