On facet-inducing inequalities for combinatorial polytopes
- Authors: Simanchev R.Y.1,2
-
Affiliations:
- Omsk Scientific Center
- Dostoevskii Omsk State University
- Issue: Vol 11, No 4 (2017)
- Pages: 564-571
- Section: Article
- URL: https://journals.rcsi.science/1990-4789/article/view/212918
- DOI: https://doi.org/10.1134/S1990478917040147
- ID: 212918
Cite item
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.
Keywords
About the authors
R. Yu. Simanchev
Omsk Scientific Center; Dostoevskii Omsk State University
Author for correspondence.
Email: osiman@rambler.ru
Russian Federation, pr. Karla Marksa 15, Omsk, 644024; pr.Mira 55A, Omsk, 644077
Supplementary files
