Integers in Boxes Problem

Question

Given positive integers $k$, $m$, $n$, with $m,n >> k$, suppose we have $n$ boxes each containing $k$ randomly (uniformly) selected positive integers $x$ satisfying $1 \leq x \leq m$ (duplicates in the box are permitted).

I begin selecting distinct positive integers $y$ such that $1 \leq y \leq m$ until one integer from each box has been selected. Call a box "marked" if at least one integer in the box has been chosen. I am interested in the expected number of $y$'s that need to be chosen until each box has been marked. At each step, a $y$ contained in the largest number of unmarked boxes is chosen.

This seems similar to some problems related to computer hashing functions (which is where it arose, though at this point the connection is a little tenuous), but I have been unable to find precisely this problem. I wonder if anyone knows the problem or sees a quick solution?

Answer 1

It sounds like the following paper should be relevant.

W. Fernandez de la Vega, V. Th. Paschos, and R. Saad, Average case analysis of a greedy algorithm for the minimum hitting set problem, LATIN '92 (São Paulo, 1992), 130–138, Lecture Notes in Comput. Sci., 583, Springer, Berlin, 1992.

Unfortunately it's behind a paywall, but the problem they study looks extremely close to yours. Your set of $y$ values is a "hitting set" because it hits every box, and your procedure for selecting $y$ values is a greedy one.