An interesting bit on the computational complexity of solving this problem (with a slightly different scoring function):

http://cstheory.stackexchange.com/questions/1854/is-finding-...