Two-lattice polyhedra

Duality and extreme points

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

Research output: Contribution to journalArticle

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

Fingerprint

Extreme Points
Polyhedron
Duality
Polymatroid
Cardinality
Intersection
Matroid Intersection
Cover
Network Flow
Fractional

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Cite this

Chang, Shiow-Yun ; Llewellyn, Donna C. ; Vande Vate, John H. / Two-lattice polyhedra : Duality and extreme points. In: Discrete Mathematics. 2001 ; Vol. 237, No. 1-3. pp. 63-95.
@article{c41c912f51984953b8bb8cfde0f1e82a,
title = "Two-lattice polyhedra: Duality and extreme points",
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.",
author = "Shiow-Yun Chang and Llewellyn, {Donna C.} and {Vande Vate}, {John H.}",
year = "2001",
month = "6",
day = "28",
doi = "10.1016/S0012-365X(00)00220-X",
language = "English",
volume = "237",
pages = "63--95",
journal = "Discrete Mathematics",
issn = "0012-365X",
publisher = "Elsevier",
number = "1-3",

}

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

In: Discrete Mathematics, Vol. 237, No. 1-3, 28.06.2001, p. 63-95.

Research output: Contribution to journalArticle

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 -