[Date Index] [Thread Index] [Author Index]

Re: Maximising a sum of matrix elements

• To: mathgroup at smc.vnet.net
• Subject: [mg60199] Re: Maximising a sum of matrix elements
• From: Bill Rowe <readnewsciv at earthlink.net>
• Date: Wed, 7 Sep 2005 04:03:57 -0400 (EDT)
• Sender: owner-wri-mathgroup at wolfram.com

On 9/5/05 at 10:27 PM, coke101 at blueyonder.co.uk (Colin Pratt) wrote:


>Could anyone suggest how I might use Mathematica to tackle the
>following?

>Given a n x n matrix with positive entries, find the maximum sum
>involving one and only one entry from each row and column. Is there
>a simple way to enumerate the n! possible sums?

I don't see why it would be needed to enumerate all possible sums. Clearly, the sum is maximized when the value of each element to sum is maximized. So, it seems to me

Total[Max/@mat] will be the maximum possible sum with only one entry from each row

and

Total[Max/@Transpose@mat]

will be the maximum possible sum with only one entry from each column.

Am I missing something?
--
To reply via email subtract one hundred and four