NP-Completeness of the Integer Balancing Problem for a Three-Dimensional Matrix

被引：3

作者：

Roublev, V. S. ^{[1
]}

Smirnov, A. V. ^{[1
]}

机构：

[1] Yaroslavl State Univ, Yaroslavl 150000, Russia

来源：

DOKLADY MATHEMATICS | 2010年 / 82卷 / 03期

关键词：

DOKLADY Mathematic; Linear Inequality; Dimensional Matrix; Cargo Transportation; Multiple Flow;

D O I：

10.1134/S1064562410060190

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

NP-completeness of the integer balancing problem for a three-dimensional matrix is studied. The integer balancing problem for a three-dimensional matrix is formulated and a three-dimensional matrix with rational elements that satisfies the balance conditions is considered. A matrix schedule of transporting empty cars, which are grouped according to certain characteristics, is also considered. The original matrix is used to construct a network with certain vertices assigned to the matrix elements and with the capacities of the network arcs assigned to these matrix elements. It is shown that the classical NP-complete problem of 3-dimensional matching can be reduced to IB3 in a polynomial time. The individual 3MM problem has a solution if and only if the IB3M problem obtained by solving the system of linear inequalities for the given set in the 3MM problem has a solution.

引用

页码：912 / 914

页数：3