TOTAL DUAL INTEGRALITY AND INTEGER POLYHEDRA

被引：61

作者：

GILES, FR

PULLEYBLANK, WR

机构：

[1] CORNELL UNIV,DEPT OPERAT RES,ITHACA,NY 14850

[2] CORE,B-3030 HEVERLEE,BELGIUM

来源：

LINEAR ALGEBRA AND ITS APPLICATIONS | 1979年 / 25卷 / 01期

关键词：

D O I：

10.1016/0024-3795(79)90018-1

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

A linear system Ax ≤ b (A, b rational) is said to be totally dual integral (TDI) if for any integer objective function c such that max {cx: Ax ≤ b} exists, there is an integer optimum dual solution. We show that if P is a polytope all of whose vertices are integer valued, then it is the solution set of a TDI system Ax ≤ b where b is integer valued. This was shown by Edmonds and Giles [4] to be a sufficient condition for a polytope to have integer vertices. © 1979.

引用

页码：191 / 196

页数：6