eTheses Repository

On the best principal submatrix problem

Lewis, Seth Charles (2007)
Ph.D. thesis, University of Birmingham.

PDF (612Kb)


Let \(A = (a_{ij})\) be an \(n \times n\) matrix with entries from \(\Re \cup \{\ -\infty\ \}\\) and \(k \in \{\ 1, \ldots ,n \}\ \). The best principal submatrix problem (BPSM) is: Given matrix \(A\) and constant \(k\), find the biggest assignment problem value from all \(k \times k\) principal submatrices of \(A\). This is equivalent to finding the (\(n-k\))'th coefficient of the max-algebraic characteristic polynomial of \(A\). It has been shown that any coefficient can be found in polynomial time if it belongs to an essential term. One application of BPSM is the job rotation problem: Given workers performing a total of \(n\) jobs, where \(a_{ij}\) is the benefit of the worker currently performing job \(i\) to instead perform job \(j\), find the maximum total benefit of rotating any \(k\) jobs round. In general, no polynomial time algorithm is known for solving BPSM (or the other two equivalent problems). BPSM and related problems will be investigated. Existing and new results will be discussed for solving special cases of BPSM in polynomial time, such as when \(A\) is a generalised permutation matrix.

Type of Work:Ph.D. thesis.
Supervisor(s):Butkovic, Peter
School/Faculty:Schools (1998 to 2008) > School of Mathematics & Statistics
Additional Information:

The paper in Appendix C is available at /

Keywords:Job Rotation Problem, Best Principal Submatrix Problem, Assignment Problem, Characteristic Max-polynomial, Max-algebraic Characteristic Polynomial, Max-algebra
Subjects:QA Mathematics
Institution:University of Birmingham
Library Catalogue:Check for printed version of this thesis
ID Code:26
This unpublished thesis/dissertation is copyright of the author and/or third parties. The intellectual property rights of the author or third parties in respect of this work are as defined by The Copyright Designs and Patents Act 1988 or as modified by any successor legislation. Any use made of information contained in this thesis/dissertation must be in accordance with that legislation and must be properly acknowledged. Further distribution or reproduction in any format is prohibited without the permission of the copyright holder.
Export Reference As : ASCII + BibTeX + Dublin Core + EndNote + HTML + METS + MODS + OpenURL Object + Reference Manager + Refer + RefWorks
Share this item :
QR Code for this page

Repository Staff Only: item control page