### Abstract

Two-lattice polyhedra are a special class of lattice polyhedra that include network flow polyhedra, fractional matching polyhedra, matroid intersection polyhedra, the intersection of two polymatroids, etc. In this paper we show that the maximum sum of components of a vector in a 2-lattice polyhedron is equal to the minimum capacity of a cover for the polyhedron. For special classes of 2-lattice polyhedra, called matching 2-lattice polyhedra, that include all of the mentioned special cases except the intersection of two polymatroids, we characterize the largest member in the family of minimum covers in terms of the maximum 'cardinality' vectors in the polyhedron. This characterization is at the heart of our extreme point algorithm (Chang et al., ISyE Technical Report No. J-94-05, ISyE, Georgia Institute of Technology, Atlanta, GA 30332) for finding a maximum cardinality vector in a matching 2-lattice polyhedron.

Original language | English |
---|---|

Pages (from-to) | 63-95 |

Number of pages | 33 |

Journal | Discrete Mathematics |

Volume | 237 |

Issue number | 1-3 |

DOIs | |

Publication status | Published - 2001 Jun 28 |

### Fingerprint

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics

### Cite this

*Discrete Mathematics*,

*237*(1-3), 63-95. https://doi.org/10.1016/S0012-365X(00)00220-X

}

*Discrete Mathematics*, vol. 237, no. 1-3, pp. 63-95. https://doi.org/10.1016/S0012-365X(00)00220-X

**Two-lattice polyhedra : Duality and extreme points.** / Chang, Shiow-Yun; Llewellyn, Donna C.; Vande Vate, John H.

Research output: Contribution to journal › Article

TY - JOUR

T1 - Two-lattice polyhedra

T2 - Duality and extreme points

AU - Chang, Shiow-Yun

AU - Llewellyn, Donna C.

AU - Vande Vate, John H.

PY - 2001/6/28

Y1 - 2001/6/28

N2 - Two-lattice polyhedra are a special class of lattice polyhedra that include network flow polyhedra, fractional matching polyhedra, matroid intersection polyhedra, the intersection of two polymatroids, etc. In this paper we show that the maximum sum of components of a vector in a 2-lattice polyhedron is equal to the minimum capacity of a cover for the polyhedron. For special classes of 2-lattice polyhedra, called matching 2-lattice polyhedra, that include all of the mentioned special cases except the intersection of two polymatroids, we characterize the largest member in the family of minimum covers in terms of the maximum 'cardinality' vectors in the polyhedron. This characterization is at the heart of our extreme point algorithm (Chang et al., ISyE Technical Report No. J-94-05, ISyE, Georgia Institute of Technology, Atlanta, GA 30332) for finding a maximum cardinality vector in a matching 2-lattice polyhedron.

AB - Two-lattice polyhedra are a special class of lattice polyhedra that include network flow polyhedra, fractional matching polyhedra, matroid intersection polyhedra, the intersection of two polymatroids, etc. In this paper we show that the maximum sum of components of a vector in a 2-lattice polyhedron is equal to the minimum capacity of a cover for the polyhedron. For special classes of 2-lattice polyhedra, called matching 2-lattice polyhedra, that include all of the mentioned special cases except the intersection of two polymatroids, we characterize the largest member in the family of minimum covers in terms of the maximum 'cardinality' vectors in the polyhedron. This characterization is at the heart of our extreme point algorithm (Chang et al., ISyE Technical Report No. J-94-05, ISyE, Georgia Institute of Technology, Atlanta, GA 30332) for finding a maximum cardinality vector in a matching 2-lattice polyhedron.

UR - http://www.scopus.com/inward/record.url?scp=0035963490&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0035963490&partnerID=8YFLogxK

U2 - 10.1016/S0012-365X(00)00220-X

DO - 10.1016/S0012-365X(00)00220-X

M3 - Article

VL - 237

SP - 63

EP - 95

JO - Discrete Mathematics

JF - Discrete Mathematics

SN - 0012-365X

IS - 1-3

ER -