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.

Volltext Dateien herunterladen

Metadaten exportieren

  • Export nach Bibtex
  • Export nach RIS

Weitere Dienste

Teilen auf Twitter Suche bei Google Scholar
Metadaten
Verfasserangaben:Nikolaus Ruf, Anita Schöbel
URN (Permalink):urn:nbn:de:hbz:386-kluedo-12696
Schriftenreihe (Bandnummer):Report in Wirtschaftsmathematik (WIMA Report) (91)
Dokumentart:Preprint
Sprache der Veröffentlichung:Englisch
Jahr der Fertigstellung:2003
Jahr der Veröffentlichung:2003
Veröffentlichende Institution:Technische Universität Kaiserslautern
Datum der Publikation (Server):11.11.2003
GND-Schlagwort:consecutive ones property; set covering; stop location
Fachbereiche / Organisatorische Einheiten:Fachbereich Mathematik
DDC-Sachgruppen:5 Naturwissenschaften und Mathematik / 51 Mathematik / 510 Mathematik
Lizenz (Deutsch):Standard gemäß KLUEDO-Leitlinien vor dem 27.05.2011

$Rev: 13581 $