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., 2016, Volume 23, Number 1, Pages 23–40 (Mi mais481)  

This article is cited in 2 scientific papers (total in 2 papers)

A special role of Boolean quadratic polytopes among other combinatorial polytopes

A. N. Maksimenko

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

Abstract: We consider several families of combinatorial polytopes associated with the following NP-complete problems: maximum cut, Boolean quadratic programming, quadratic linear ordering, quadratic assignment, set partition, set packing, stable set, $3$-assignment. For comparing two families of polytopes we use the following method. We say that a family $P$ is affinely reduced to a family $Q$ if for every polytope $p\in P$ there exists $q\in Q$ such that $p$ is affinely equivalent to $q$ or to a face of $q$, where $\dim q = O((\dim p)^k)$ for some constant $k$. Under this comparison the above-mentioned families are splitted into two equivalence classes. We show also that these two classes are simpler (in the above sense) than the families of polytopes of the following problems: set covering, traveling salesman, $0$-$1$ knapsack problem, $3$-satisfiability, cubic subgraph, partial ordering. In particular, Boolean quadratic polytopes appear as faces of polytopes in every mentioned families.
Article is published in the author's wording.

Keywords: NP-hard problems, affine reduction, faces of polytopes.

Funding Agency Grant Number
Ministry of Education and Science of the Russian Federation 477
Supported by the project No. 477 of P.G. Demidov Yaroslavl State University within State Assignment for Research.


DOI: https://doi.org/10.18255/1818-1015-2016-1-23-40

Full text: PDF file (605 kB)
References: PDF file   HTML file

Bibliographic databases:

UDC: 519.854.33
Received: 15.11.2015
Language:

Citation: A. N. Maksimenko, “A special role of Boolean quadratic polytopes among other combinatorial polytopes”, Model. Anal. Inform. Sist., 23:1 (2016), 23–40

Citation in format AMSBIB
\Bibitem{Mak16}
\by A.~N.~Maksimenko
\paper A special role of Boolean quadratic polytopes among other combinatorial polytopes
\jour Model. Anal. Inform. Sist.
\yr 2016
\vol 23
\issue 1
\pages 23--40
\mathnet{http://mi.mathnet.ru/mais481}
\crossref{https://doi.org/10.18255/1818-1015-2016-1-23-40}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=3502273}
\elib{http://elibrary.ru/item.asp?id=25475539}


Linking options:
  • http://mi.mathnet.ru/eng/mais481
  • http://mi.mathnet.ru/eng/mais/v23/i1/p23

    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

    This publication is cited in the following articles:
    1. A. N. Maksimenko, “On a family of 0/1-polytopes with an NP-complete criterion for vertex nonadjacency relation”, Discrete Math. Appl., 29:1 (2019), 7–14  mathnet  crossref  crossref  isi  elib
    2. A. N. Maksimenko, “Bulev kvadratichnyi mnogogrannik yavlyaetsya granyu mnogogrannika lineinykh poryadkov”, Sib. elektron. matem. izv., 14 (2017), 640–646  mathnet  crossref
  • Моделирование и анализ информационных систем
    Number of views:
    This page:132
    Full text:61
    References:49

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