Applying Lehman's theorems to packing problems
type: Item
instance of: scholarly article
title: Applying Lehman's theorems to packing problems
zbMATH Open document ID: 0863.05052
DOI: 10.1007/BF01590960
published in: Mathematical Programming. Series A. Series B
publication date: 1996-09-18T00:00:00Z
review text: A matrix \(A\) is ideal if the polyhedron \(\{x\in Q^V \mid A \cdot x\geq 1\) and \(x\geq 0\}\) is integral, and perfect if the polyhedron \(\{x\in Q^V \mid A \cdot x\leq 1\) and \(x\geq 0\}\) is integral. The author gives a bijection between superclasses of the classes of ideal and perfect matrices, obtaining new results on packing polyhedra and stable set polytopes of near-bipartite graphs (deletion of any neighbourhood results in a bipartite graph) and some other classes of graphs.
Mathematics Subject Classification ID: 05C50
Mathematics Subject Classification ID: 52B12
zbMATH DE Number: 910017
zbMATH Keywords: ideal matrix
zbMATH Keywords: blocking matrix
zbMATH Keywords: total dual integrability
zbMATH Keywords: perfect matrices
zbMATH Keywords: packing polyhedra
zbMATH Keywords: stable set polytopes
author: F. Bruce Shepherd
reviewed by: Christoph Schulz
MaRDI profile type: Publication
cites work: Finite checkability for integer rounding properties in combinatorial programming problems
cites work: Graphical properties related to minimal imperfection
cites work: Q3220614
cites work: On certain polytopes associated with graphs
cites work: Ideal 0, 1 matrices
cites work: Bottleneck extrema
cites work: Matrices with the Edmonds-Johnson property
cites work: On stable set polyhedra for K//(1,3)free graphs
cites work: A generalization of antiwebs to independence systems and their canonical facets
cites work: On the width—length inequality
cites work: Q3973409
cites work: Normal hypergraphs and the perfect graph conjecture
cites work: Perfect zero–one matrices
cites work: Almost integral polyhedra related to certain combinatorial optimization problems
cites work: Lehman's forbidden minor characterization of ideal 0-1 matrices
cites work: Q4234148
cites work: Q3818127
cites work: The Forbidden Minors of Binary Clutters
cites work: Q3973410
cites work: Near-perfect matrices
cites work: Perfect triangle-free 2-matchings
description: scientific article; zbMATH DE number 910017