Consider that you have n counters initialised with numbers $M_1 \dots M_n$. In each round you decrement exactly $k$ out of these counters. Keep doing this until at least $n-k+1$ counters are zero, so you can't continue. Determine the maximum number of rounds.

This can be illustrated with muffins, e.g. 18 nuts, 12 apple, 10 chocolate, 9 blueberry available. Form a maximum number of plates @ 3 different muffins each.

One can solve this with a greedy approach which always decrements the k largest counters. The proof that this is optimal is not hard but also non obvious.

My question is under what name this apparently rather natural question appears in the literature.

  • 2
    $\begingroup$ It's quite similar to en.wikipedia.org/wiki/Havel%E2%80%93Hakimi_algorithm. In fact, I think it is probably a special case of it, as you can add $N$ vertices of degree $N-1+k$ to the counters, where $N$ is a large enough number. (This would be just the first step of some reduction, we need more gadgets.) $\endgroup$ – domotorp Nov 22 '17 at 19:39
  • 2
    $\begingroup$ In a way, this is an instance of $k$-dimensional matching (matching in a $k$-uniform hypergraph). In particular, the number of vertices is the initial sum of the counters (i.e. one vertex per "muffin") and the hyperedges connect vertices of different types (i.e. every combination of $k$ different muffins defines an edge). $\endgroup$ – Mikhail Rudoy Nov 23 '17 at 7:08
  • $\begingroup$ "Degree Sequences of Uniform Hypergraphs" looks like a promising Google term. $\endgroup$ – Jukka Suomela Nov 23 '17 at 20:32
  • 1
    $\begingroup$ The greedy algorithm is not polynomial-time in the length of the input, if the input is presented in binary. $\endgroup$ – usul Nov 25 '17 at 16:46

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.