|
This article is cited in 1 scientific paper (total in 1 paper)
On facet-inducing inequalities for combinatorial polytopes
R. Yu. Simanchevab a Omsk Scientific Center SB RAS, 15 Karl Marx Ave., 644024 Omsk, Russia
b Dostoevsky Omsk State University, 55A Mira Ave., 630077 Omsk, Russia
Abstract:
One of the central questions of polyhedral combinatorics is the question of the algorithmic relationship between the vertex and facet descriptions of convex polytopes. From the standpoint of combinatorial optimization, the main reason for the actuality of this question is the possibility of applying the methods of convex analysis to solving the extremal combinatorial problems. In this paper, we consider the combinatorial polytopes of a sufficiently general form. We obtain a few of necessary conditions and a sufficient condition for a supporting inequality of a polytope to be a facet inequality and give an illustration of the use of the developed technology to the polytope of some graph approximation problem. Bibliogr. 20.
Keywords:
polytope, facet, $M$-graph, supporting inequality.
Received: 18.01.2017 Revised: 12.05.2017
Citation:
R. Yu. Simanchev, “On facet-inducing inequalities for combinatorial polytopes”, Diskretn. Anal. Issled. Oper., 24:4 (2017), 95–110; J. Appl. Industr. Math., 11:4 (2017), 564–571
Linking options:
https://www.mathnet.ru/eng/da884 https://www.mathnet.ru/eng/da/v24/i4/p95
|
Statistics & downloads: |
Abstract page: | 471 | Full-text PDF : | 55 | References: | 31 | First page: | 8 |
|