{"id":{"repo_id":"birmingham","oai_identifier":"oai:etheses.bham.ac.uk:26"},"canonical_url":"https://search.dev.ndltd.org/etd/birmingham/oai:etheses.bham.ac.uk:26","repository":{"repo_id":"birmingham","name":"University of Birmingham","base_url":"https://etheses.bham.ac.uk/cgi/oai2"},"display":{"title":"On the best principal submatrix problem","abstract":"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.","abstract_html":"Let <span class=\"etd-inline-math\">A = (a<sub>ij</sub>)</span> be an \\(n \\times n\\) matrix with entries from <span class=\"etd-inline-math\">\\Re \\cup \\{ -\\infty \\}\\</span> and <span class=\"etd-inline-math\">k \\in \\{ 1, \\ldots ,n \\} </span>. 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\\))&#x27;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 <span class=\"etd-inline-math\">a<sub>ij</sub></span> 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.","abstract_has_math":true,"creators":["Lewis, Seth Charles"],"institution":"University of Birmingham","degree_name":"d_ph","degree_level":"d_ph","degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2007,"date_issued":"2007-07","date_published":"2007-07","updated_at":"2026-07-24T01:10:41Z","subjects":["QA Mathematics"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":null,"outbound_label":null,"outbound_source":null},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.sponsor","label":"Sponsor","values":["na"]},{"key":"dc:creator","label":"Author","values":["Lewis, Seth Charles"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2007-07"]},{"key":"dc:date.issued","label":"Date","values":["2007-07"]},{"key":"dc:publisher.department","label":"Dc Publisher Department","values":["School of Mathematics & Statistics","School of Mathematics"]},{"key":"dc:publisher.institution","label":"Dc Publisher Institution","values":["University of Birmingham"]},{"key":"dc:relation.isreferencedby","label":"Dc Relation Isreferencedby","values":["http://etheses.bham.ac.uk//id/eprint/26/"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"dc:type.qualificationlevel","label":"Dc Type Qualificationlevel","values":["d_ph"]},{"key":"dc:type.qualificationname","label":"Dc Type Qualificationname","values":["d_ph"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["QA Mathematics"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://etheses.bham.ac.uk//id/eprint/26/1/Lewis07PhD.pdf","http://etheses.bham.ac.uk//id/eprint/26/2/Decl_IS_Lewis07PhD.pdf"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["On the best principal submatrix problem"]}]}],"canonical_facts":{"dc:contributor.sponsor":["na"],"dc:creator":["Lewis, Seth Charles"],"dc:date":["2007-07"],"dc:date.issued":["2007-07"],"dc:description.abstract":["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."],"dc:format":["application/pdf"],"dc:identifier.uri":["http://etheses.bham.ac.uk//id/eprint/26/1/Lewis07PhD.pdf","http://etheses.bham.ac.uk//id/eprint/26/2/Decl_IS_Lewis07PhD.pdf"],"dc:publisher.department":["School of Mathematics & Statistics","School of Mathematics"],"dc:publisher.institution":["University of Birmingham"],"dc:relation.isreferencedby":["http://etheses.bham.ac.uk//id/eprint/26/"],"dc:subject":["QA Mathematics"],"dc:title":["On the best principal submatrix problem"],"dc:type":["Thesis"],"dc:type.qualificationlevel":["d_ph"],"dc:type.qualificationname":["d_ph"]},"updated_at":"2026-07-24T01:10:41Z"}