Greedy algorithm Packing problem

Assume that $$A$$ is the set of objects such that each object $$x_i \in A$$ has value $$w_i$$. We wish to pack these objects into group, each pack containing at least $$k$$ objects. Our goal is to minimize the maximum difference between the maximum and minimum value of each packs. in other words, our goal is to minimize $$L$$ with the constraint that all packs should have more than $$k$$ object in them.

$$L = \max_{i \in \mathrm{packs}} \left\{\max_{j \in \mathrm{pack}(i)}w_j - \min_{k \in \mathrm{pack}(i)}w_k \right\}.$$

For example for the following packing, $$L$$ is $$\max{(30-20, 120 - 100)} = 20$$. $$[20, 30] \;\; [100,110,120]$$

I was wondering if there is a greedy algorithm that can do the job.

• I don't know if greedy can do the entire job optimally, but here's a small hint: There's an important property to be exploited here that rules out a large class of solutions from optimality, enabling an $O(n^2)$ DP solution. – j_random_hacker Apr 1 at 16:15
• I think using the fact that in the optimal answer, the last pack should contain at most $2k-1$ objects (a pack with $2k$ objects can be split in two packs with $k$ objects) we can construct the $O(n^2)$ DP solution. – user102344 Apr 2 at 7:48

I would not believe there is a greedy algorithm that can do the job. Instead, sorting followed by dynamic programming as indicated by j_random_hacker's comment seems the appropriate way to find $$L$$.

Let $$n$$ be the number of given objects. Assume $$k\le n$$; otherwise there is no such packing.

First, sort all the weights so that we will have $$w_0\le w_2\le \cdots\le w_{n-1}$$. Then there is an optimal packing in which each pack consists of consecutive weights. That fact enables dynamic programming, since we can consider only that kind of packing, which has a natural last pack.

Given a packing $$P$$, let $$L(P)$$ be the maximum difference between the maximum and minimum value of each pack in $$P$$. Let $$dp[i]$$ be the minimum of $$L(P)$$ for all packings of the weights $$w_0, w_1,\cdots, w_i$$, where $$k-1\le i\le n-1$$. The final answer for all $$n$$ weights is $$dp[n-1]$$.

The base case is $$dp[i] = w_i-w_0$$ for $$k-1\le i\lt 2k-1$$, as there can be only one pack that contains all the weights.

What if $$i\ge 2k-1$$? Note that a packing with its last pack removed is still a packing. That critical observation tells us that $$dp[i]$$ is the minimum of \begin{align} &\max(dp[i-k],\ w_i-w_{(i-k)+1}), \\ &\max(dp[i-k-1],\ w_i-w_{(i-k-1)+1}), \\ &\max(dp[i-k-2],\ w_i-w_{(i-k-2)+1}), \\ &\cdots,\\ &\max(dp[i-k-\ell],\ w_i-w_{(i-k-\ell)+1}), \\ &\cdots, \end{align} where the list stops right before $$\ell$$ becomes $$k$$, since we can ignore the packings where the last pack (in fact, any pack) contains at least $$2k$$ objects. We can always split those objects into 2 valid packs, which will not increase $$L(P)$$. We can also stop as soon as $$w_i-w_{(i-k-\ell)+1}$$ is no less than the minimum so far.

The time-complexity of algorithm is $$O(n\log n + nk)$$.