# Simplified Maximum Diversity Problem

The Maximum Diversity Problem calls for choosing $m$ items from a list of $n$ items, such that the diversity defined as some metric distance between items is maximized.

I have a simpler problem, which I was hoping I could solve in a simpler manner. In my case I have a list of $n$ items each with a certain non-unique key. I want to chose $m$ items from my list so that the maximal number of items per key is minimized.

e.g., if my list is:

('a', 5), ('b', 4), ('c', 2), ('a', 6), ('b', 5)


and we must choose $m=3$ items, an optimal solution would be a list containing one item for each key.

Is there an algorithm for doing this that is simpler than those for the Maximum Diversity Problem?

• What have you tried? Where did you get stuck? We do not want to just hand you the solution; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? You may also want to check out our reference questions. – Raphael Aug 13 '16 at 19:22
• @Raphael - I'm not a CS major, so my own research led me to read about the Maximum Diversity Problem, but this does seem to be a bit of an overkill. I have some heuristics I thought of, but I don't think they're very efficient. This is a real life problem I'm encountering, not an assignment of any sort. – nbubis Aug 13 '16 at 19:30
• If there are $k$ different keys then the pigeonhole principle implies that your maximum diversity is at least $\lceil m/k \rceil$; and this is achievable. – Yuval Filmus Aug 13 '16 at 20:24
• @Yuvalfilmus - True. The question is how. – nbubis Aug 13 '16 at 20:32
• Actually I take it back that it's always achievable. But it seems that a greedy strategy should work. – Yuval Filmus Aug 13 '16 at 20:48

The following algorithm should work.

The algorithm proceeds in several rounds. At each round, let $m'$ be the number of remaining items to take. Take one item per key, up to $m'$ items, and remove these items. If we took $m'$ items, the algorithm terminates. Otherwise, continue to the next round.

We leave the correctness proof (or a counterexample) to the reader.

• Thanks! I added my own answer which should give the same solution in a single pass. – nbubis Aug 14 '16 at 13:39

Thinking about it a a bit more, I think I have a "one pass" algorithm for solving this.

Let there be $n$ items with $k$ keys, with $n_i$ items for each key. We want to choose $m_i\le n_i$, such that $\sum m_i = m$, and that $\max{m_i}$ is minimized.

Clearly, if for all $n_i$ we have $n_i > m/k$, we simply choose $m_i = m/k$. Otherwise, we use the following algorithm:

1. Count the number of items for each key ($n_i$) and sort them in ascending order.
2. While $n_i \le m/k$ set $m_i=n_i$
3. For all $n_i > m/k$, choose $m_i = \left\lceil \frac{m - \sum_{j<i} m_j}{k-i+1}\right\rceil$

This algorithm should be $O(n)$ in the length of the list, assuming the number of different keys is negligible in comparison.