Refine
Document Type
- Preprint (2)
- Diploma Thesis (1)
Language
- English (3) (remove)
Has Fulltext
- yes (3)
Keywords
- consecutive ones property (3) (remove)
Faculty / Organisational entity
In this paper we consider set covering problems with a coefficient matrix almost having the consecutive ones property, i.e., in many rows of the coefficient matrix, the ones appear consecutively. If this property holds for all rows it is well known that the set covering problem can be solved efficiently. For our case of almost consecutive ones we present a reformulation exploiting the consecutive ones structure to develop bounds and a branching scheme. Our approach has been tested on real-world data as well as on theoretical problem instances.
Matrices with the consecutive ones property and interval graphs are important notations in the field of applied mathematics. We give a theoretical picture of them in first part. We present the earliest work in interval graphs and matrices with the consecutive ones property pointing out the close relation between them. We pay attention to Tucker's structure theorem on matrices with the consecutive ones property as an essential step that requires a deep considerations. Later on we concentrate on some recent work characterizing the matrices with the consecutive ones property and matrices related to them in the terms of interval digraphs as the latest and most interesting outlook on our topic. Within this framework we introduce a classiffcation of matrices with consecutive ones property and matrices related to them. We describe the applications of matrices with the consecutive ones property and interval graphs in different fields. We make sure to give a general view of application and their close relation to our studying phenomena. Sometimes we mention algorithms that work in certain fields. In the third part we give a polyhedral approach to matrices with the consecutive ones property. We present the weighted consecutive ones problem and its relation to Tucker's matrices. The constraints of the weighted consecutive ones problem are improved by introducing stronger inequalities, based on the latest theorems on polyhedral aspect of consecutive ones property. Finally we implement a separation algorithm of Oswald and Reinhelt on matrices with the consecutive ones property. We would like to mention that we give a complete proof to the theorems when we consider important within our framework. We prove theorems partially when it is worthwhile to have a closer look, and we omit the proof when there are is only an intersection with our studying phenomena.