for some upper bound u**, representing the data miner's capacity.**
Interestingly, this problem can be reduced to the (weighted) budgeted maximum coverage problem **(Khuller et al, 1999), which is a weighted variant of**
the maximum set coverage problem. In that problem, a universe of elements is given and with each element a weight is associated. Furthermore, a collection of subsets of the universe is given, each of which has a specified cost. The task is to select a set of subsets from the collection so as to maximize the sum of the weights of the elements in the union of these selected subsets, while **respecting** an upper bound on the sum of the costs of the selected subsets.

To reduce our tile mining problem to the budgeted maximum coverage problem, the elements in the universe are the database entries that are **equal to 1.**
The collection of subsets is given by the collection of all tiles present in the database. The weight of the database entry at position (i, j**) is equal to the**
contribution it makes to the information content of a tile containing it, equal to
− log(pij **). And the cost of a tile is equal to its description length.**
The budgeted maximum coverage problem is a hard combinatorial problem.

Fortunately, it can be approximated well by using an efficient greedy **algorithm**
(see Khuller et al (1999) for details). The criterion to greedily select a tile τk for inclusion as k'th tile in the set is the ratio of the sum of the weights − **log(**pij ) of database entries (i, j) ∈ τk **not yet contained in earlier selected tiles, versus**
the description length of τk**. Formally, with**

$$\begin{array}{r c l}{{\mathrm{SelfInformation}^{+}(\tau_{k})}}&{{=}}&{{-}}\\ {{}}&{{}}&{{}}\\ {{}}&{{}}&{{(i,j)\in\tau_{k}\mathrm{~and~}(i,j)\not\in\tau\::l<k}}\end{array}\log(p_{i j}),$$

in iteration k of the greedy algorithm selects the tile τk **maximizing the CompressionRatio**+(τk)
defined as follows:

$$+\left(\pi_{k}\right)$$

## Compressionratio+(Τk) = **Selfinformation**+(Τk) Descriptionlength(Τk) .

In the first iteration, this selection criterion coincides with the interestingness measure CompressionRatio(τ**) as defined earlier, thus corroborating our choice**
for the this ratio as interestingness measure.

Note that upon selection of a tile τk in iteration k**, the CompressionRatio**+(τ)
of any other yet unselected tile can only decrease. This can be exploited by the algorithm by keeping all yet unselected tiles in a sorted list, sorted according to their last updated value of SelfInformation+(τ**). Then, to select the next best**
tile, the tile at the top of this list is considered and the updated value of its CompressionRatio+(τ**) is computed. If this value is still larger than the subsequent tile in the list, we can be sure it will remain so even after all subsequent**
ones are updated too, and it can be selected as the k **+ 1'st tile. Otherwise, it**
must be inserted in the list to keep it sorted, and the second tile in the **list is**
considered. This powerful idea was first introduced in Minoux (1978).

The approximation quality of this greedy algorithm is such that any set of k **top-ranked tiles in this list has a self-information that is at least 1** −
1 e times the maximum self-information that can be achieved by a set of tiles with