- INSTANCE:
Nonnegative symmetric
matrices
*A*and*B*. - SOLUTION:
A permutation
.
- MEASURE:
.

*Bad News:*At least as hard as MINIMUM TRAVELING SALESPERSON [31].*Comment:*If one of the matrices satisfies the triangle inequality, the problem is approximable within [31].