Two-lattice polyhedra: Duality and extreme points

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

研究成果: Article同行評審

4 引文 斯高帕斯(Scopus)

摘要

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.

原文English
頁(從 - 到)63-95
頁數33
期刊Discrete Mathematics
237
發行號1-3
DOIs
出版狀態Published - 2001 六月 28

All Science Journal Classification (ASJC) codes

  • 理論電腦科學
  • 離散數學和組合

指紋

深入研究「Two-lattice polyhedra: Duality and extreme points」主題。共同形成了獨特的指紋。

引用此