4
$\begingroup$

Suppose I have four sets A={0, 4, 9}, B={2, 6, 11}, C={3, 8, 13}, and D={7, 12}.

I need to choose exactly one number from each of these sets, so that the difference between the largest and smallest chosen numbers is as small as possible.

What type of problem is this? Is there a graph algorithm that could be used to solve this problem?

$\endgroup$
4
  • $\begingroup$ Is this question really about groups or is it actually about sets? $\endgroup$ Aug 25 '12 at 20:29
  • 2
    $\begingroup$ Edited for clarity $\endgroup$
    – Jeffε
    Aug 26 '12 at 1:38
  • 1
    $\begingroup$ the tags seem random $\endgroup$ Aug 26 '12 at 16:11
  • $\begingroup$ I hope you enjoyed seeing people do duplicate work, but that is against some vague ethics. Please refrain from it in the future. $\endgroup$ Aug 27 '12 at 15:06
10
$\begingroup$

It's not really a graph problem, I think. Problems in which you try to choose some objects to minimize the difference between the min and max chosen object are called "minimum range" problems — e.g. look up "minimum range cut", which is a graph problem — but this one looks like you're trying to find the minimum range basis of a partition matroid with one partition set for each of your groups.

In general minimum range matroid basis problems can be solved in $O(n\log n)$ time, plus $O(n)$ steps of a subroutine that finds a basis of a set with corank one: sort the elements from smallest to largest and then process the elements one by one. While you process the elements maintain an independent set $I$; when you process an element $e$, add $e$ to $I$ and, if that addition causes $I$ to become dependent, kick out the minimum weight element in the unique circuit of $I$. The minimum range basis is one of the sets $I$ that you found in this process: the one that has full rank and has as small a range between min and max as possible.

For your partition matroid special case it's easy to find the circuit in $I$ when it becomes dependent: a circuit happens when $e$ belongs to the same group as an element $f$ that you previously added, and $f$ is the element you should kick out of $I$. So the whole algorithm takes $O(n\log n)$ time, or possibly faster depending on how much time it takes to do the sorting step.

$\endgroup$

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.