Partition a set into k groups with minimum number of moves

Question

You have a set of n objects for which integer positions are given. A group of objects is a set of objects at the same position (not necessarily all the objects at that position: there might be multiple groups at a single position). The objects can be moved to the left or right, and the goal is to move these objects so as to form k groups, and to do so with the minimum distance moved.

For example:

• With initial positions at [4,4,7], and k = 3: the minimum cost is 0.
• [4,4,7] and k = 2: minimum cost is 0
• [1,2,5,7] and k = 2: minimum cost is 1 + 2 = 3

I've been trying to use a greedy approach (by calculating which move would be shortest) but that wouldn't work because every move involves two elements which could be moved either way. I haven't been able to formulate a dynamic programming approach as yet but I'm working on it.

Answer 1

Let's look at k=1.

For k=1 and n odd, all points should move to the center point. For k=1 and n even, all points should move to either of the center points or any spot between them. By 'center' I mean in terms of number of points to either side, i.e. the median.

You can see this because if you select a target spot, x, with more points to its right than it's left, then a new target 1 to the right of x would result in a cost reduction (unless there is exactly one more point to the right than the left and the target spot is a point, in which case n is even and the target is on/between the two center points).

If your points are already sorted, this is an O(1) operation. If not, I believe it's O(n) (via an order statistic algorithm).

Once you've found the spot that all points are moving to, it's O(n) to find the cost.

Thus regardless of whether the points are sorted or not, this is O(n).

Answer 2

This problem is a one-dimensional instance of the k-medians problem, which can be stated as follows. Given a set of points x_1...x_n, partition these points into k sets S_1...S_k and choose k locations y_1...y_k in a way that minimizes the sum over all x_i of |x_i - y_f(i)|, where y_f(i) is the location corresponding of the set to which x_i is assigned.

Due to the fact that the median is the population minimizer for absolute distance (i.e. L_1 norm), it follows that each location y_j will be the median of the elements x in the corresponding set S_j (hence the name k-medians). Since you are looking at integer values, there is the technicality that if S_j contains an even number of elements, the median might not be an integer, but in such cases choosing either the next integer above or below the median will give the same sum of absolute distances.

The standard heuristic for solving k-medians (and the related and more common k-means problem) is iterative, but this is not guaranteed to produce an optimal or even good solution. Solving the k-medians problem for general metric spaces is NP-hard, and finding efficient approximations for k-medians is an open research problem. Googling "k-medians approximation", for example, will lead to a bunch of papers giving approximation schemes. http://www.cis.upenn.edu/~sudipto/mypapers/kmedian_jcss.pdf http://graphics.stanford.edu/courses/cs468-06-winter/Papers/arr-clustering.pdf

In one dimension things become easier, and you can use a dynamic programming approach. A DP solution to the related one-dimensional k-means problem is described in this paper, and the source code in R is available here. See the paper for details, but the idea is essentially the same as what @SajalJain proposed, and can easily be adapted to solve the k-medians problem rather than k-means. For j<=k and m<=n let D(j,m) denote the cost of an optimal j-medians solution to x_1...x_m, where the x_i are assumed to be in sorted order. We have the recurrence

D(j,m) = min (D(j-1,q) + Cost(x_{q+1},...,x_m)

where q ranges from j-1 to m-1 and Cost is equal to the sum of absolute distances from the median. With a naive O(n) implementation of Cost, this would yield an O(n^3k) DP solution to the whole problem. However, this can be improved to O(n^2k) due to the fact that the Cost can be updated in constant time rather than computed from scratch every time, using the fact that, for a sorted sequence:

Cost(x_1,...,x_h) = Cost(x_2,...,x_h) + median(x_1...x_h)-x_1   if h is odd
Cost(x_1,...,x_h) = Cost(x_2,...,x_h) + median(x_2...x_h)-x_1   if h is even

See the writeup for more details. Except for the fact that the update of the Cost function is different, the implementation will be the same for k-medians as for k-means. http://journal.r-project.org/archive/2011-2/RJournal_2011-2_Wang+Song.pdf

Answer 3

Task 0 - sort the position of the objects in non-decreasing order

Let us define 'center' as the position of the object where it is shifted to.

Now we have two observations;

1. For N positions the 'center' would be the position which is nearest to the mean of these N positions. Example, let 1,3,6,10 be the positions. Then mean = 5. Nearest position is 6. Hence the center for these elements is 6. This gives us the position with minimum cost of moving when all elements need to be grouped into 1 group.

2. Let N positions be grouped into K groups "optimally". When N+1 th object is added, then it will disturb only the K th group, i.e, first K-1 groups will remain unchanged.

From these observations, we build a dynamic programming approach.

Let Cost[i][k] and Center[i][k] be two 2D arrays. 
Cost[i][k] = minimum cost when first 'i' objects are partitioned into 'k' groups
Center[i][k] stores the center of the 'i-th' object when Cost[i][k] is computed.

Let {L} be the elements from i-L,i-L+1,..i-1 which have the same center.
(Center[i-L][k] = Center[i-L+1][k] = ... = Center[i-1][k])
These are the only objects that need to be considered in the computation for i-th element (from observation 2)

Now

Cost[i][k] will be 
min(Cost[i-1][k-1] , Cost[i-L-1][k-1] + computecost(i-L, i-L+1, ... ,i))
Update Center[i-L ... i][k]

computecost() can be found trivially by finding the center (from observation 1)

Time Complexity:

Sorting O(NlogN)
Total Cost Computation Matrix = Total elements * Computecost = O(NK * N)
Total = O(NlogN + N*NK) = O(N*NK)

Answer 4

as I understand, the problems is:

we have n points on a line. we want to place k position on the line. I call them destinations. move each of n points to one of the k destinations so the sum of distances is minimum. I call this sum, total cost. destinations can overlap.

An obvious fact is that for each point we should look for the nearest destinations on the left and the nearest destinations on the right and choose the nearest.

Another important fact is all destinations should be on the points. because we can move them on the line to right or to left to reach a point without increasing total distance.

By these facts consider following DP solution:

DP[i][j] means the minimum total cost needed for the first i point, when we can use only j destinations, and have to put a destination on the i-th point.

to calculate DP[i][j] fix the destination before the i-th point (we have i choice), and for each choice (for example k-th point) calculate the distance needed for points between the i-th point and the new point added (k-th point). add this with DP[k][j - 1] and find the minimum for all k.

the calculation of initial states (e.g. j = 1) and final answer is left as an exercise!