On the Set-Covering Problem

Egon Balas and Manfred W. Padberg
Additional contact information
Manfred W. Padberg: Carnegie-Mellon University, Pittsburgh, Pennsylvania

Operations Research, 1972, vol. 20, issue 6, 1152-1161

Abstract: This paper establishes some useful properties of the equality-constrained set-covering problem P and the associated linear program P ′. First, the Dantzig property of transportation matrices is shown to hold for a more general class of matrices arising in connection with adjacent integer solutions to P ′. Next, we show that, for every feasible integer basis to P ′, there are at least as many adjacent feasible integer bases as there are nonbasic columns. Finally, given any two basic feasible integer solutions x 1 and x 2 to P ′, x 2 can be obtained from x 1 by a sequence of p pivots (where p is the number of indices j ϵ N for which x j 1 is nonbasic and x j 2 = 1), such that each solution in the associated sequence is feasible and integer. Some of our results have been conjectured earlier by A ndrew , H offmann , and K rabek in a paper presented to ORSA in 1968.

Date: 1972
References: Add references at CitEc
Citations: View citations in EconPapers (14)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.20.6.1152 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:20:y:1972:i:6:p:1152-1161

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().