6
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @Haile: No questions? If you think this does not answer your question, can you clarify what exactly is your question? $\endgroup$ – Aryabhata Apr 21 '13 at 2:28
  • $\begingroup$ Yes, the reduction was from, it was a language mistake. Yep, your answer is clear. Thank you! $\endgroup$ – Haile Apr 21 '13 at 13:02
  • $\begingroup$ Nice solution. But your answer still doesn't resolve the complexity of this problem. We just know that its in P now. $\endgroup$ – rizwanhudda Apr 23 '13 at 20:39
  • $\begingroup$ @rizwanhudda: Yes, I never claimed optimality of the solution. $\endgroup$ – Aryabhata Apr 23 '13 at 20:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.