Integer partition weighted minimum of maximum

Question

Given a non-negative integer $n$ and a positive real weight vector $w$ with dimension $m$, partition $n$ into a length-$m$ non-negative integer vector that sums to $n$ (call it $v$) such that $\max w_iv_i$ is the smallest, that is, we want to find the vector $v$ such that the maximum of element-wise product between $w$ and $v$ is the smallest. There maybe several partitions, and we only want the smallest value of $\max w_iv_i$ among all possible $v$.

Seems like this problem can use a greedy algorithm to solve. From any target vector $v$ for $n-1$, we add 1 to each entry, and find the minimum among those $m$ vectors. but I don't think it's correct. The intuition is that it might add "over" the minimum. That is, there exists another partition not yielded by the add 1 procedure that falls in between the "minimum" of $n-1$ produced by this greedy algorithm and that of $n$ produced by this greedy algorithm. Can anyone prove if this is correct or incorrect?

Answer 1

You can solve the problem via integer linear programming (ILP) as follows. Let $z$ represent $\max_i v_i$. The problem is to minimize $z$ subject to \begin{align} z &\ge w_i v_i &&\text{for $i\in\{1,\dots,m\}$} \\ \sum_{i=1}^m v_i &= n \\ v_i &\in \mathbb{Z}^+ &&\text{for $i\in\{1,\dots,m\}$} \end{align}

If your greedy algorithm is not optimal, solving the ILP formulation can help find a counterexample.