CODEWITHSUNDEEP
algorithmmatrix
yxmm
yxmm

Reputation: 21

Minimizing difference of min & max column sums of a matrix

Given a matrix (non-square) of positive integers, where all elements on the same row are permutable, the problem is to minimize the difference between the maximum and minimum sums of columns.

For example,

  9  5  7        5  7  9      
  9  3  4   ~>   9  4  3
 10  5  9        5 10  9
----------      ----------
 28 13 20       19 21 21

 28-13= 15      21-19= 2

where the answer is 2.

I tried to naively sort it (combining min & max values on adjacent rows), which gives correct results for small matrices like 3x3, but what can work for bigger data (up to ~30x30)? Is there a generic solution I couldn't apply?

Upvotes: 2

Views: 730

Answers (1)

templatetypedef
templatetypedef

Reputation: 372784

This problem is, unfortunately, NP-hard via a reduction from the partition problem. In the partition problem, you're given a list of numbers and want to determine whether there's a way to split those numbers into two disjoint groups so that the sums of those numbers are equal.

You can encode an instance of the partition problem as an instance of your problem as follows: create an n × 2 matrix where each row contains one of the numbers from the set and a 0. For example, given the set {1, 3, 5, 7, 9}, you'd make the matrix

1 0
3 0
5 0
7 0
9 0

If you think about it, permuting the rows here will give back two columns that can be thought of as the two sets that you've partitioned the numbers into. If the minimum difference between the columns is 0, then the set can be partitioned into two equal subsets. If it isn't, then the set can't be partitioned. Minimizing the difference between the min and the max column, therefore, would therefore allow you to solve the partition problem as a special case.

Since this problem is NP-hard, then unless P = NP, you won't be able to find any simple polynomial-time algorithms for solving it. You may be able to develop some heuristics to beat brute-force solutions, though.

Hope this helps!

Upvotes: 3

Related Questions