Local ratio method on partial set multi-cover

Yingli Ran, Yishuo Shi and Zhao Zhang ()
Additional contact information
Yingli Ran: Xinjiang University
Yishuo Shi: Xinjiang University
Zhao Zhang: Zhejiang Normal University

Journal of Combinatorial Optimization, 2017, vol. 34, issue 1, No 21, 302-313

Abstract: Abstract In this paper, we study the minimum partial set multi-cover problem (PSMC). Given an element set E, a collection of subsets $${\mathcal {S}}\subseteq 2^E$$ S ⊆ 2 E , a cost $$c_S$$ c S on each set $$S\in {\mathcal {S}}$$ S ∈ S , a covering requirement $$r_e$$ r e for each element $$e\in E$$ e ∈ E , and an integer k, the PSMC problem is to find a sub-collection $${\mathcal {F}}\subseteq {\mathcal {S}}$$ F ⊆ S to fully cover at least k elements such that the cost of $${\mathcal {F}}$$ F is as small as possible, where element e is fully covered by $${\mathcal {F}}$$ F if it belongs to at least $$r_e$$ r e sets of $${\mathcal {F}}$$ F . This paper presents an approximation algorithm using local ratio method achieving performance ratio $$\max \left\{ \frac{\Delta }{k}\left( \frac{1}{f-r_{\min }}+\frac{r_{\max }}{r_{\min }}\right) ,\frac{1}{\rho }+\frac{f}{r_{\min }}+\frac{1}{r_{\max }}-\frac{1}{\rho r_{\max }}-1,\frac{1}{\rho }\right\} $$ max Δ k 1 f - r min + r max r min , 1 ρ + f r min + 1 r max - 1 ρ r max - 1 , 1 ρ , where $$\Delta $$ Δ is the size of a maximum set, f is the maximum number of sets containing a common element, $$\rho $$ ρ is the minimum percentage of elements required to be fully covered during iterations of the algorithm, and $$r_{\max }$$ r max and $$r_{\min }$$ r min are the maximum and the minimum covering requirement, respectively. In particular, when $$r_{\max }$$ r max is a constant, the first term can be omitted. Notice that our ratio coincides with the classic ratio f for both the set multi-cover problem (in which case $$k=|E|$$ k = | E | ) and the partial set single-cover problem (in which case $$r_{\max }=1$$ r max = 1 ). However, when $$k 1$$ r max > 1 , the ratio might be as large as $$\Theta (n)$$ Θ ( n ) . This result shows an interesting “shock wave like” feature of approximating PSMC. The purpose of this paper is trying to arouse some interest in such a feature and attract more work on this challenging problem.

Keywords: Partial set multicover; Local ratio; Approximation algorithm (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-016-0066-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:jcomop:v:34:y:2017:i:1:d:10.1007_s10878-016-0066-0

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-016-0066-0

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().