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

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

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

<p>My question is under what name this apparently rather natural question appears in the literature.</p>

CC BY-SA 3.0
2017-11-25T16:46:08.230Z
The greedy algorithm is not polynomial-time in the length of the input, if the input is presented in binary.
usul
CC BY-SA 3.0
2017-11-22T19:39:48.797Z
It's quite similar to https://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.)
domotorp
CC BY-SA 3.0
2017-11-23T07:08:24.050Z
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).
Mikhail Rudoy
CC BY-SA 3.0
2017-11-23T20:32:03.473Z
"Degree Sequences of Uniform Hypergraphs" looks like a promising Google term.
Jukka Suomela
<reference-request><optimization><greedy-algorithms>
Which well-known algorithmic problem is this an instance of?
Martin Hofmann
# Which well-known algorithmic problem is this an instance of?

(Asked by: username_0 on 2017-11-22)

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.

**Tags:** reference-request, optimization, greedy-algorithms

> **Comments:**
> **username_2**: It's quite similar to https://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.)  
> **username_3**: 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).  
> **username_4**: "Degree Sequences of Uniform Hypergraphs" looks like a promising Google term.  
> **username_1**: The greedy algorithm is not polynomial-time in the length of the input, if the input is presented in binary.  

---

## 0 answers

