The Extended Budgeted Maximum
Coverage Problem
The Extended Budgeted Maximum Coverage
(EBMC) problem is a generalization of the Budgeted Maximum Coverage (BMC)[R1]
problem, which generalize the set in BMC to fuzzy set. Also, it can be seen as
a specific case of the Generalized Maximum Coverage (GMC)[R2] problem.
Let 
be a collection of fuzzy sets defined
over a domain of elements 
. Each fuzzy set
has a cost 
while each element has a weight 
. 
is defined as the grade of membership of 
in 
. The goal is to
find a collection of fuzzy sets 
, such that the
total cost of 
, denoted by 
, does not exceed
a given budget 
, while the total
weight 
is maximized. and are defined by the following formulae,
respectively.
Approximation algorithm
Here we provide a 
-approximation algorithm form EBMC, which is first mentioned in
[P1]. The time complexity of this algorithm is 
, where 𝑚=|𝑆| and 𝑛=|𝑋|.
|
|
|
|
[P1]
Jiwei Ding, Wentao Ding, Wei Hu and Yuzhong Qu. 2015. An EBMC-Based Approach to
Selecting Types for Entity Filtering. AAAI-15 In press.
[Download this paper] [Download supplemental material]
References
[R1]
Khuller, S.; Moss, A.; and Naor, J. 1999. The budgeted maximum coverage
problem. Information Processing Letters 70(1):39–45.
[R2]
Cohen, R., and Katzir, L. 2008. The generalized maximum coverage problem.
Information Processing Letters 108(1):15–22.