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.
|
PDF
967kB |
| 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: | https://purl.utwente.nl/essays/92296 |
| Export this item as: | BibTeX EndNote HTML Citation Reference Manager |
Show download statistics for this publication
Show download statistics for this publicationRepository Staff Only: item control page