• search hit 6 of 17
Back to Result List

Set Covering With Almost Consecutive Ones Property

  • 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.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Author:Nikolaus Ruf, Anita Schöbel
URN (permanent link):urn:nbn:de:hbz:386-kluedo-12696
Serie (Series number):Report in Wirtschaftsmathematik (WIMA Report) (91)
Document Type:Preprint
Language of publication:English
Year of Completion:2003
Year of Publication:2003
Publishing Institute:Technische Universität Kaiserslautern
Date of the Publication (Server):2003/11/11
GND-Keyword:consecutive ones property; set covering; stop location
Faculties / Organisational entities:Fachbereich Mathematik
DDC-Cassification:5 Naturwissenschaften und Mathematik / 510 Mathematik
Licence (German):Standard gemäß KLUEDO-Leitlinien vor dem 27.05.2011