7
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Raphael Aug 13 '16 at 19:22
  • $\begingroup$ @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. $\endgroup$ – nbubis Aug 13 '16 at 19:30
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Aug 13 '16 at 20:24
  • $\begingroup$ @Yuvalfilmus - True. The question is how. $\endgroup$ – nbubis Aug 13 '16 at 20:32
  • $\begingroup$ Actually I take it back that it's always achievable. But it seems that a greedy strategy should work. $\endgroup$ – Yuval Filmus Aug 13 '16 at 20:48
3
$\begingroup$

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.

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

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.

$\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.