University of Twente Student Theses


Structure of and algorithms for binary staircase matrices

Dissel, L. van (2022) Structure of and algorithms for binary staircase matrices.

[img] PDF
Abstract:Staircase structures play an important role in many optimization problems involving linear programs. It has become apparent that systems with this characteristic structure can be solved in linear time, as opposed to standard linear programs which are usually less efficient. Recognizing a staircase structure can therefore be of great importance. This paper focuses specifically on binary matrices containing this characteristic structure. We say that a binary matrix is in staircase form if every 2-by-2 submatrix with 1s in the off-diagonal entries is the all-1s submatrix and the 1s in every row and column are consecutive. A binary matrix is staircase if its rows and columns can be permuted such that the resulting matrix is in staircase form. This paper investigates the structure of these staircase matrices from a graph-theoretic viewpoint and describes an improved linear-time algorithm that computes the staircase form of a given matrix or returns that the given matrix is not staircase.
Item Type:Essay (Bachelor)
Faculty:EEMCS: Electrical Engineering, Mathematics and Computer Science
Subject:31 mathematics
Programme:Applied Mathematics BSc (56965)
Link to this item:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page