[Solved]: Time Complexity of a selection problem

Problem Detail: 

I wonder what's the time complexity of the following selection problem I found while thinking of a string-matching problem.

[Assuming operations on integers take $O(1)$ time]

We are Given $m$ sets, with $n$ integer numbers each. We want to select exactly one integer from each set, to make a set S, such that $~ l = \max(S) - \min(S)~$ is minimized.

For example, n = 4, m = 3:

$S_1 = \{1, 43, 71, 101\}$

$S_2 = \{18, 53, 80, 107\}$

$S_3 = \{3, 16, 51, 208\}$

Now

$~S = \{43, 53, 51\}$

has one number from each set and

$~l = \max(S) - \min(S) = 53 - 43 = 10 ~$

wich is the minimum possible value of $l$ (I think).

First thing I tried was a reduction to the set cover problem, but I wasn't able to find one.

Asked By : Haile

Answered By : Aryabhata

If you are trying to prove $NP$-Hardness of that problem, you need a reduction from (not to).

Anyway, I don't think this is $NP$-hard (unless $P = NP$, of course)

Suppose the $S_i$ are sorted.

Suppose you decide that element $x \in S_j$ will be minimum. Now in each other set, you can find the smallest element greater (or equal to) $x$ using binary search, and take the maximum among those.

Do this for each of the $mn$ numbers, assuming it is the minimum. Pick the best set you get. This gives you a polynomial time algorithm: $m \log n$ time for each of the $mn$ elements, giving an $O(m^2n \log n)$ time algorithm.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/11424

3.2K people like this

 Download Related Notes/Documents