• Deutsch
    • English
  • English 
    • Deutsch
    • English
  • Login
 
View Item 
  •   Home
  • Naturwissenschaften, Mathematik und Informatik
  • Fakultät für Mathematik und Informatik
  • View Item
  •   Home
  • Naturwissenschaften, Mathematik und Informatik
  • Fakultät für Mathematik und Informatik
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Set covering with almost consecutive ones property

Ruf, N. ; Schöbel, Anita

Citable Link (URL):http://resolver.sub.uni-goettingen.de/purl?gs-1/5715
Anthology Article (Submitted version)
04-Ruf-Sch-DO.pdf (186.1Kb)
  
First published (peer reviewed)
In: Megiddo, Nimrod (Eds.) Discrete Optimization
Elsevier, 2004
Google Scholar Lookup
Abstract
In this paper, we consider set covering problems with a coefficient matrix almost having the consecutive ones property, i.e., in most rows of the coefficient matrix, the ones appear consecutively and only a few blocks of consecutive ones appear in the remaining rows. 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.

Metadaten-Export

Teilen


Contact Us | Send Feedback | Imprint | Guidelines | Datenschutzhinweis
Development and operation by the Lower Saxon State and university Library of Göttingen
 

 

Browse

All of GoeScholarInstitutionsIssue DateAuthorsTitlesThis CollectionIssue DateAuthorsTitles

More Offers

Lecture Series at the University

Help & Info

Help & FAQUpload ServiceLicensesOA-Publication Funds

Contact Us | Send Feedback | Imprint | Guidelines | Datenschutzhinweis
Development and operation by the Lower Saxon State and university Library of Göttingen