On the job rotation problem
Peter Butkovic and Seth Lewis
School of Mathematics
The University of Birmingham
Edgbaston
Birmingham B15 2TT
United Kingdom
August 26, 2006
Abstract
The job rotation problem (JRP) is the following: Given an n × n
matrix A over R ∪ {-∞} and k ≤ n, find a k × 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.
Keywords: principal submatrix, assignment problem, job rotation
problem, node disjoint cycles.
AMS-classification: 15A15, 90C27
1 Introduction
One of the classical problems in combinatorial optimization is the (linear) as-
signment problem which can be described as follows: A one-to-one assignment
between two n-element sets of objects, say {A1 , ..., An} and {B1, ..., Bn} has to
be found. The cost cij of assigning Ai to Bj is given for every pair (Ai , Bj ) and
the task is to find an assignment that minimises the total cost. This problem
has a convenient matrix formulation: If we store the coefficients cij in an n × n
matrix C then the assignment problem means to choose n entries of C so that
no two are from the same row or column, and their sum is minimal.
The assignment problem has, of course, also a maximising form in which
the coefficients represent benefits and the object is to maximise the sum of the
More intriguing information
1. The name is absent2. The name is absent
3. Determinants of Household Health Expenditure: Case of Urban Orissa
4. Income Growth and Mobility of Rural Households in Kenya: Role of Education and Historical Patterns in Poverty Reduction
5. The name is absent
6. Palvelujen vienti ja kansainvälistyminen
7. Deletion of a mycobacterial gene encoding a reductase leads to an altered cell wall containing β-oxo-mycolic acid analogues, and the accumulation of long-chain ketones related to mycolic acids
8. Getting the practical teaching element right: A guide for literacy, numeracy and ESOL teacher educators
9. Restructuring of industrial economies in countries in transition: Experience of Ukraine
10. The Impact of Financial Openness on Economic Integration: Evidence from the Europe and the Cis