On fractional faces of the metric polytope |
| |
Authors: | V. A. Bondarenko A. V. Nikolaev |
| |
Affiliation: | 1.Demidov Yaroslavl State University,Yaroslavl,Russia |
| |
Abstract: | The integrality recognition problem is considered on a sequence M n, k of nested relaxations of a Boolean quadric polytope, including the rooted semimetric M n and metric M n, 3 polytopes. The constraints of the metric polytope cut off all faces of the rooted semimetric polytope that contain only fractional vertices. This makes it possible to solve the integrality recognition problem on M n in polynomial time. To solve the integrality recognition problem on the metric polytope, we consider the possibility of cutting off all fractional faces of M n, 3 by a certain relaxation M n, k . The coordinates of points of the metric polytope are represented in homogeneous form as a three-dimensional block matrix. We show that in studying the question of cutting off the fractional faces of the metric polytope, it is sufficient to consider only constraints in the form of triangle inequalities. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|