Balanced matrices and the set covering polytope
Joint Authors
Source
The Arabian Journal for Science and Engineering
Issue
Vol. 16, Issue 2B (s) (30 Jun. 1991), pp.269-282, 14 p.
Publisher
King Fahd University of Petroleum and Minerals
Publication Date
1991-06-30
Country of Publication
Saudi Arabia
No. of Pages
14
Main Subjects
Abstract EN
A (0>l)-matrix is said to be balanced if it does not contain any submatrix of odd order with exactly two ones in each row and each column.
A well-known necessary (but not sufficient) condition for a (0,l)-matrix A to be balanced is that the polytope associated with the linear programming relaxation of the set covering Problem associated with A has only integral vertices.
In this paper we characterize a class of (0,l)-matrices A for which the above condition is also sufficient for A to be balanced.
This provides at the same time a new class of facet defining inequalities for the general set covering polytope, where the coeffjcjents can arbjtrary elements in {0, 1, ..., p), the p being a specified positive integer.
Some applications to the Krcover problem and Kj-perfect graphs are also discussed.
American Psychological Association (APA)
Eulerf, R.& Mahjub, A. R.. 1991. Balanced matrices and the set covering polytope. The Arabian Journal for Science and Engineering،Vol. 16, no. 2B (s), pp.269-282.
https://search.emarefa.net/detail/BIM-395169
Modern Language Association (MLA)
Eulerf, R.& Mahjub, A. R.. Balanced matrices and the set covering polytope. The Arabian Journal for Science and Engineering Vol. 16, no. 2B (s) (Jun. 1991), pp.269-282.
https://search.emarefa.net/detail/BIM-395169
American Medical Association (AMA)
Eulerf, R.& Mahjub, A. R.. Balanced matrices and the set covering polytope. The Arabian Journal for Science and Engineering. 1991. Vol. 16, no. 2B (s), pp.269-282.
https://search.emarefa.net/detail/BIM-395169
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references : p. 282
Record ID
BIM-395169
