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, 2017 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$ Nov 23, 2017 at 7:08
  • $\begingroup$ "Degree Sequences of Uniform Hypergraphs" looks like a promising Google term. $\endgroup$ Nov 23, 2017 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, 2017 at 16:46


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.