<p>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 <a href="http://en.wikipedia.org/wiki/Partition_matroid">partition matroid</a> with one partition set for each of your groups.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2012-08-25T18:35:30.197Z
2012-08-25T18:35:30.197Z
David Eppstein
<p>Suppose I have four sets A={0, 4, 9}, B={2, 6, 11}, C={3, 8, 13}, and D={7, 12}.</p>

<p>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. </p>

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

CC BY-SA 3.0
2012-08-25T20:29:51.910Z
Is this question really about groups or is it actually about sets?
Tyson Williams
CC BY-SA 3.0
2012-08-26T01:38:28.547Z
Edited for clarity
Jeffε
CC BY-SA 3.0
2012-08-26T16:11:18.767Z
the tags seem random
Sasho Nikolov
CC BY-SA 3.0
2012-08-27T15:06:30.913Z
I hope you enjoyed seeing people do duplicate work, but that is against some vague ethics.  Please refrain from it in the future.
Tsuyoshi Ito
<ds.algorithms><graph-algorithms>
Choosing one number from each set so that the difference between maximum and minimum is minimized
user1624525
# Choosing one number from each set so that the difference between maximum and minimum is minimized

(Asked by: username_0 on 2012-08-25)

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?

**Tags:** ds.algorithms, graph-algorithms

> **Comments:**
> **username_1**: Is this question really about groups or is it actually about sets?  
> **username_2**: Edited for clarity  
> **username_3**: the tags seem random  
> **username_4**: I hope you enjoyed seeing people do duplicate work, but that is against some vague ethics.  Please refrain from it in the future.  

---

## 1 answers

### Answer by username_5 on 2012-08-25. Score: 10 | Accepted answer

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](http://en.wikipedia.org/wiki/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.


---

