Hypergraphs of Special Type and CUT Polytope Relaxations Properties Analysis

Modelirovanie i Analiz Informacionnyh Sistem. 2011;18(3):82-100


Journal Homepage

Journal Title: Modelirovanie i Analiz Informacionnyh Sistem

ISSN: 1818-1015 (Print); 2313-5417 (Online)

Publisher: Yaroslavl State University

Society/Institution: P.G. Demidov Yaroslavl State University

LCC Subject Category: Technology: Technology (General): Industrial engineering. Management engineering: Information technology

Country of publisher: Russian Federation

Language of fulltext: Russian, English

Full-text formats available: PDF



A. V. Nikolaev (Ярославский государственный университет им. П.Г. Демидова)


Double blind peer review

Editorial Board

Instructions for authors

Time From Submission to Publication: 8 weeks


Abstract | Full Text

The topic of the research is a relationship between a class of hypergraphs of a special type and properties of the points of the cut polytope relaxations $M_{n,k}$. It is established that for a sufficiently large $n$ in $M_{n,4}$ and $M_{n,5}$ polytopes, there are points which have no integer vertices in any expansion in a convex combination of $M_{n,3}$ vertices.