On the job rotation problem

The job rotation problem (JRP) is the following: Given an n×nn×n matrix AA over R∪{−∞}R∪{−∞} and k≤nk≤n, find a k×kk×k principal submatrix of AA whose optimal assignment problem value is maximum. No polynomial algorithm is known for solving this problem if kk is an input variable. We analyse JRP and present polynomial solution methods for a number of special cases.