On the job rotation problem

Peter Butkovic, Seth Lewis

Research output: Contribution to journalArticlepeer-review

7 Citations (Scopus)
186 Downloads (Pure)


The job rotation problem (JRP) is the following: Given an n x n matrix A over \(\Re ∪ {-∞} and kn, find a k x k principal submatrix of A whose optimal assignment problem value is maximum. No polynomial algorithm is known for solving this problem if k is an input variable. We analyse JRP and present polynomial solution methods for a number of special cases.

Original languageEnglish
Pages (from-to)163-174
Number of pages12
JournalDiscrete Optimization
Issue number2
Early online date13 Dec 2006
Publication statusPublished - 1 Jun 2007


  • principal submatrix
  • assignment problem
  • job rotation problem
  • node disjoint cycles


Dive into the research topics of 'On the job rotation problem'. Together they form a unique fingerprint.

Cite this