RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Model. Anal. Inform. Sist.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Model. Anal. Inform. Sist., 2014, Volume 21, Number 4, Pages 25–34 (Mi mais384)  

Some Properties of Metric Polytope Constraints

V. A. Bondarenko, A. V. Nikolaev

P. G. Demidov Yaroslavl State University, Sovetskaya str., 14, Yaroslavl, 150000, Russia

Abstract: The integrality recognition problem is considered on the sequence $M_{n, k}$ of the nested Boolean quadric polytope relaxations, including the rooted semimetric $M_{n}$ and the metric $M_{n,3} $ polytopes. Constraints of the metric polytope cut off all faces of the rooted semimetric polytope, containing only fractional vertices, that allows to solve the problem of integrality recognition on $M_{n}$ in polynomial time. To solve the problem of integrality recognition on the metric polytope, we consider the possibility of cutting off all fractional faces of $M_{n, 3}$ by some relaxation $M_{n,k}$. We represent the coordinates of the metric polytope in a homogeneous form by a three-dimensional block matrix. We show that to answer the question of the metric polytope fractional faces cutting off, it is sufficient to consider only constraints of the triangle inequalities form.

Keywords: integrality recognition, rooted semimetric polytope, metric polytope, relaxation polytope.

Full text: PDF file (430 kB)
References: PDF file   HTML file
UDC: 519.16+514.172.45
Received: 28.07.2014

Citation: V. A. Bondarenko, A. V. Nikolaev, “Some Properties of Metric Polytope Constraints”, Model. Anal. Inform. Sist., 21:4 (2014), 25–34

Citation in format AMSBIB
\Bibitem{BonNik14}
\by V.~A.~Bondarenko, A.~V.~Nikolaev
\paper Some Properties of Metric Polytope Constraints
\jour Model. Anal. Inform. Sist.
\yr 2014
\vol 21
\issue 4
\pages 25--34
\mathnet{http://mi.mathnet.ru/mais384}


Linking options:
  • http://mi.mathnet.ru/eng/mais384
  • http://mi.mathnet.ru/eng/mais/v21/i4/p25

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Моделирование и анализ информационных систем
    Number of views:
    This page:152
    Full text:49
    References:38

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020