Breaking thermaxBarrier: Enhanced Approximation Algorithms for Partial Set Multicover Problem

DOI10.1287/ijoc.2020.0975OpenAlexW3092807993MaRDI QIDQ4995101

Shaojie Tang, Ding-Zhu Du, Zhao Zhang, Yingli Ran

Publication date: 23 June 2021

Published in: INFORMS Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/ijoc.2020.0975

zbMATH Keywords

approximation algorithmpartial set multicoverminimum \(k\) union

Mathematics Subject Classification ID

Mathematical programming (90Cxx)

Related Items (4)

Constant Approximation for the Lifetime Scheduling Problem of p-Percent Coverage ⋮ An improved approximation algorithm for the \(k\)-prize-collecting minimum power cover problem ⋮ A primal-dual approximation algorithm for the \(k\)-prize-collecting minimum power cover problem ⋮ Approximation algorithm for minimum partial multi-cover under a geometric setting

Cites Work

• Improved performance of the greedy algorithm for partial cover
• Approximation algorithm for partial positive influence problem in social network
• On positive influence dominating sets in social networks
• Complexity of finding dense subgraphs
• Approximation algorithm for the partial set multi-cover problem
• On the approximability of positive influence dominating set in social networks
• 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
• Local ratio method on partial set multi-cover
• Submodular functions and optimization.
• Using Homogeneous Weights for Approximating the Partial Cover Problem
• Public-key cryptography from different assumptions
• Detecting high log-densities
• Approximation Algorithms for Hypergraph Small Set Expansion and Small Set Vertex Expansion
• The Densest $k$-Subhypergraph Problem
• The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema
• Positive Influence Dominating Set in Online Social Networks
• Primal-Dual RNC Approximation Algorithms for Set Cover and Covering Integer Programs
• Minimizing the Union: Tight Approximations for Small Set Bipartite Vertex Expansion
• Approximation algorithm for partial set multicover versus full set multicover
• Approximation algorithms for partial covering problems
• Approximating Steiner Networks with Node-Weights
• Combinatorial optimization. Theory and algorithms.
• The dense \(k\)-subgraph problem

This page was built for publication: Breaking ther_maxBarrier: Enhanced Approximation Algorithms for Partial Set Multicover Problem