The complexity of recognizing linear systems with certain integrality properties

被引：27

作者：

Ding, Guoli ^{[1
]}

Feng, Li ^{[2
]}

Zang, Wenan ^{[2
]}

机构：

[1] Louisiana State Univ, Dept Math, Baton Rouge, LA 70803 USA

[2] Univ Hong Kong, Dept Math, Hong Kong, Hong Kong, Peoples R China

来源：

MATHEMATICAL PROGRAMMING | 2008年 / 114卷 / 02期

基金：

美国国家科学基金会;

关键词：

linear system; polyhedron; total dual integrality; NP-hardness;

D O I：

10.1007/s10107-007-0103-y

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

Let A be a 0 - 1 matrix with precisely two 1's in each column and let 1 be the all-one vector. We show that the problems of deciding whether the linear system Ax >= 1, x >= 0 (1) defines an integral polyhedron, (2) is totally dual integral (TDI), and (3) box-totally dual integral (box-TDI) are all co-NP-complete, thereby confirming the conjecture on NP-hardness of recognizing TDI systems made by Edmonds and Giles in 1984.

引用

页码：321 / 334

页数：14

共 15 条

[1]

Berge C, 1976, Graphs and Hypergraphs

[2]

Bondy J.A., 2008, GRAD TEXTS MATH

[3] Recognizing Berge graphs [J].

Chudnovsky, M ;

Cornuéjols, G ;

Liu, XM ;

Seymour, P ;

Vuskovic, K .

COMBINATORICA, 2005, 25 (02) :143-186

[4] The strong perfect graph theorem [J].

Chudnovsky, Maria ;

Robertson, Neil ;

Seymour, Paul ;

Thomas, Robin .

ANNALS OF MATHEMATICS, 2006, 164 (01) :51-229

[5] CERTAIN POLYTOPES ASSOCIATED WITH GRAPHS [J].

CHVATAL, V .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1975, 18 (02) :138-154

[6]

COOK W, 1984, MATH PROGRAM STUD, V22, P64, DOI 10.1007/BFb0121008

[7]

Cornuejols G., 2001, Combinatorial Optimization: Packing and Covering

[8]

Edmonds J, 1984, Progress in Combinatorial Optimization, P117, DOI DOI 10.1016/B978-0-12-566780-7.50013-1

[9]

Edmonds J, 1977, Annals of Discrete Mathematics, V1, P185

[10]

Fulkerson DR, 1971, MATH PROGRAM, V1, P168

← 1 2 →