Back to search

University of Birmingham

Integrality in max-linear systems

Abstract

dc:description.abstract

This thesis deals with the existence and description of integer solutions to max-linear systems. It begins with the one-sided systems and the subeigenproblem. The description of all integer solutions to each of these systems can be achieved in strongly polynomial time. The main max-linear systems that we consider include the eigenproblem, and the problem of determining whether a matrix has an integer vector in its column space. Also the two-sided systems, as well as max-linear programming problems. For each of these problems we construct algorithms which either find an integer solution, or determine that none exist. If the input matrix is finite, then the algorithms are proven to run in pseudopolynomial time. Additionally, we introduce special classes of input matrices for each of these problems for which we can determine existence of an integer solution in strongly polynomial time, as well as a complete description of all integer solutions. Moreover we perform a detailed investigation into the complexity of the problem of finding an integer vector in the column space. We describe a number of equivalent problems, each of which has a polynomially solvable subcase. Further we prove NP-hardness of related problems obtained by introducing extra conditions on the solution set.

Degree

thesis:*
Name dc:type.qualificationname
d_ph
Level dc:type.qualificationlevel
d_ph
Grantor dc:publisher.institution
University of Birmingham
Year dc:date.issued
2015

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • MacCaig, Marie

Subjects

dc:subject × 1

Rights

Language dc:language.dcterms_iso639_2
eng

Chain of custody

source
Harvested from
University of Birmingham
Base URL
etheses.bham.ac.uk/cgi/oai2
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

MacCaig, Marie. Integrality in max-linear systems. d_ph thesis, University of Birmingham, 2015.