Breaking the r max Barrier: Enhanced Approximation Algorithms for Partial Set Multicover Problem

Yingli Ran (), Zhao Zhang (), Shaojie Tang () and Ding-Zhu Du ()
Additional contact information
Yingli Ran: College of Mathematics and Computer Sciences, Zhejiang Normal University, Jinhua, Zhejiang 321004, China
Zhao Zhang: College of Mathematics and Computer Sciences, Zhejiang Normal University, Jinhua, Zhejiang 321004, China
Shaojie Tang: Naveen Jindal School of Management, University of Texas at Dallas, Richardson, Texas 75080
Ding-Zhu Du: Department of Computer Science, University of Texas at Dallas, Richardson, Texas 75080

INFORMS Journal on Computing, 2021, vol. 33, issue 2, 774-784

Abstract: Given an element set E of order n , a collection of subsets S ⊆ 2 E , a cost c S on each set S ∈ S , a covering requirement r e for each element e ∈ E , and an integer k , the goal of a minimum partial set multicover problem (MinPSMC) is to find a subcollection F ⊆ S to fully cover at least k elements such that the cost of F is as small as possible and element e is fully covered by F if it belongs to at least r e sets of F . This problem generalizes the minimum k -union problem (Min k U) and is believed not to admit a subpolynomial approximation ratio. In this paper, we present a ( 4 log ⁡ n H ( Δ ) In k + 2 ⁡ log n n ) -approximation algorithm for MinPSMC, in which Δ is the maximum size of a set in S . And when k = Ω ( n ) , we present a bicriteria algorithm fully covering at least ( 1 − ε 2 log n ) k elements with approximation ratio O ( 1 ε ( log n ) 2 H ( Δ ) ) , where 0 < ε < 1 is a fixed number. These results are obtained by studying the minimum density subcollection problem with (or without) cardinality constraint, which might be of interest by itself.

Keywords: partial set multicover; minimum k union; approximation algorithm (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2020.0975 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:33:y:2021:i:2:p:774-784

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().