从全幺模到平衡0,±1矩阵:一类整数多面体

From Totally Unimodular to Balanced 0, ±1 Matrices: A Family of Integer Polytopes

Mathematics of Operations Research · 1994
被引 8
ABS 3

中文导读

本文引入了一类整数多面体,并通过禁止子矩阵刻画其特征,其两个极端情形分别对应约束矩阵为全幺模和平衡矩阵,推广了Truemper-Chandrasekaran与Conforti-Cornuéjols的结果。

Abstract

In this paper we introduce a family of integer polytopes and characterize them in terms of forbidden submatrices. The two extreme cases in this family arise when the constraint matrix is totally unimodular and balanced, respectively. This generalizes results of Truemper-Chandrasekaran and Conforti-Cornuéjols.

整数规划组合优化矩阵理论多面体组合