Breaking thermaxBarrier: Enhanced Approximation Algorithms for Partial Set Multicover Problem

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

INFORMS Journal on Computing · 2021 · Volume 33 · Issue 2

DOI: 10.1287/ijoc.2020.0975

Abstract

Given an element set E of order n , a collection of subsets 𝑆 ⊆ 2 𝐸 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 l o g ⁡ 𝑛 ⁢ 𝐻 ⁡ ( 𝛥 ) ⁢ I n 𝑘 + 2 ⁡ l o g 𝑛 ⁢ √ 𝑛 ) ( 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 l o g 𝑛 ) 𝑘 ( 1 − ε 2 log n ) k elements with approximation ratio 𝑂 ⁡ ( 1 𝜀 ⁢ ( l o g 𝑛 ) 2 𝐻 ⁡ ( Δ ) ) O ⁡ ( 1 ε ⁢ ( log n ) 2 H ⁡ ( Δ ) ) , where 0 < 𝜀 < 1 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

Enable JavaScript for citation tools and additional paper interactions.