Minimum power partial cover meets fairness: improved approximation guarantees

DOI10.1007/S10878-026-01477-6MaRDI QIDQ7406199zbMATH OpenFDO

Authors Chensheng Ma, Mingchao Zhou, Qingye Shou, Zhao Zhang

Publication date 2026

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/S10878-026-01477-6

zbMATH Keywords

approximation algorithmfairness constraintpartial coverpower coverprice of fairnessprimal-dual

Mathematics Subject Classification ID

Mathematical programming (90Cxx)

Cites work

• A constant-factor approximation for multi-covering with disks
• A constant-factor approximation for multi-covering with disks
• A note on multicovering with disks
• A note on the minimum power partial cover problem on the plane
• A primal-dual algorithm for the minimum power partial cover problem
• A primal-dual approximation algorithm for the \(k\)-prize-collecting minimum power cover problem
• Achieving long-term fairness in submodular maximization through randomization
• Algorithms for the online power cover problem on a line
• Algorithms – ESA 2005
• An approximation algorithm for the H-prize-collecting power cover problem
• Approximation algorithm for fair stochastic maximum coverage problem
• Approximation algorithm for minimum power partial multi-coverage in wireless sensor networks
• Approximation algorithm for prize-collecting hypergraph vertex cover with fairness constraints
• Approximation algorithm for prize-collecting vertex cover with fairness constraints
• Approximation algorithm for prize-collecting weighted set cover with fairness constraints
• Approximation algorithm for vertex cover with multiple covering constraints
• Approximation algorithms for the minimum power cover problem with submodular/linear penalties
• Approximation algorithms for the minimum power partial cover problem
• Approximation algorithms for the partition set cover problem with penalties
• Approximation algorithms for the partition vertex cover problem
• Approximation and Online Algorithms
• Clustering to minimize the sum of cluster diameters
• Fairness in graph-theoretical optimization problems
• Fairness through awareness
• Fault-tolerant covering problems in metric spaces
• Group fairness in non-monotone submodular maximization
• scientific article; zbMATH DE number 1445293 (Why is no real title available?)
• scientific article; zbMATH DE number 7064055 (Why is no real title available?)
• Minimum power partial cover with fairness constraint
• Minimum power partial multi-cover on a line
• Minimum-cost coverage of point sets by disks
• Multi cover of a polygon minimizing the sum of areas
• On colorful vertex and edge cover problems
• Optimal coverage in wireless sensor networks
• Polynomial time approximation schemes for base station coverage with minimum total radii

This page was built for publication: Minimum power partial cover meets fairness: improved approximation guarantees

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