Finding Max Product in NxM Matrix Without Duplicate Rows/Cols

[Chuck37]

I'd like to find a simple algorithm to do the following.

If I have an NxM matrix, with N≥M, find the M entries with the maximum product that do not share a row or column.

It doesn't seem hard, but I'm not seeing it right off.

 

[chiro]

Hey Chuck37.

I've never heard of the maximum product: can you outline what this corresponds to?

 

[Alcatrace IV]

Wait, do you mean the maximum product as simply the result of multiplying the greatest non-intersecting plots of a MN matrix? Just to clarify

For example, in the 6-schematized matrix:

(1) (2)
(3) (4)
(5) (6)

the maximum product would be (5)(4) = 20 etc.

 

[uart]

I'm not sure what it physically corresponds to, but it sounds like an interesting problem.

Well let's start with brute force. If N,M are not too large you could try all \frac{n!}{(n-m)!} combinations.

There might be a nice neat algorithm that does this really cleanly, but if that "ideal" algorithm can't be found then modifying brute force to add heuristics might work out ok.

 

[AlephZero]

This sems a very hard problem if the matrix entries can be either positive or negative, because a positive maximum value might involve some negative elements of the matrix. It's hard to see how to solve that except by brute force.

If you want to think about more efficient searching strategies, it would probably be better to restruct the problem to positive numbers.

 

[Chuck37]

Sorry I'm just getting back to this after the weekend. The values inside are probabilities and thus always positive. I have brute force currently implemented, but when the matrix gets big, there are a lot of combinations and since I have to do it a lot, it adds up.

Maximum product was intended just how it sounds, the N entries that when multiplied together give the biggest values - with no entries sharing a row or column (the example from Alcatrace IV is right). At this point I'd be happy with something that is close most of the time since I need speed.