Two-lattice polyhedra: Duality and extreme points

Shiow Yun Chang, Donna C. Llewellyn, John H. Vande Vate

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)

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 languageEnglish
Pages (from-to)63-95
Number of pages33
JournalDiscrete Mathematics
Volume237
Issue number1-3
DOIs
Publication statusPublished - 2001 Jun 28

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'Two-lattice polyhedra: Duality and extreme points'. Together they form a unique fingerprint.

Cite this