A Special Role of Boolean Quadratic Polytopes among Other Combinatorial Polytopes
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 us...
Saved in:
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Yaroslavl State University
2016-02-01
|
| Series: | Моделирование и анализ информационных систем |
| Subjects: | |
| Online Access: | https://www.mais-journal.ru/jour/article/view/304 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849338766369488896 |
|---|---|
| author | A. N. Maksimenko |
| author_facet | A. N. Maksimenko |
| author_sort | A. N. Maksimenko |
| collection | DOAJ |
| description | 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 |
| format | Article |
| id | doaj-art-5a1f3471ad3048488ec20f29b98aa032 |
| institution | Kabale University |
| issn | 1818-1015 2313-5417 |
| language | English |
| publishDate | 2016-02-01 |
| publisher | Yaroslavl State University |
| record_format | Article |
| series | Моделирование и анализ информационных систем |
| spelling | doaj-art-5a1f3471ad3048488ec20f29b98aa0322025-08-20T03:44:18ZengYaroslavl State UniversityМоделирование и анализ информационных систем1818-10152313-54172016-02-01231234010.18255/1818-1015-2016-1-23-40280A Special Role of Boolean Quadratic Polytopes among Other Combinatorial PolytopesA. N. Maksimenko0P.G. Demidov Yaroslavl State University, Sovetskaya str., 14, Yaroslavl, 150000, RussiaWe 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 familyhttps://www.mais-journal.ru/jour/article/view/304np-hard problemsaffine reductionfaces of polytopes |
| spellingShingle | A. N. Maksimenko A Special Role of Boolean Quadratic Polytopes among Other Combinatorial Polytopes Моделирование и анализ информационных систем np-hard problems affine reduction faces of polytopes |
| title | A Special Role of Boolean Quadratic Polytopes among Other Combinatorial Polytopes |
| title_full | A Special Role of Boolean Quadratic Polytopes among Other Combinatorial Polytopes |
| title_fullStr | A Special Role of Boolean Quadratic Polytopes among Other Combinatorial Polytopes |
| title_full_unstemmed | A Special Role of Boolean Quadratic Polytopes among Other Combinatorial Polytopes |
| title_short | A Special Role of Boolean Quadratic Polytopes among Other Combinatorial Polytopes |
| title_sort | special role of boolean quadratic polytopes among other combinatorial polytopes |
| topic | np-hard problems affine reduction faces of polytopes |
| url | https://www.mais-journal.ru/jour/article/view/304 |
| work_keys_str_mv | AT anmaksimenko aspecialroleofbooleanquadraticpolytopesamongothercombinatorialpolytopes AT anmaksimenko specialroleofbooleanquadraticpolytopesamongothercombinatorialpolytopes |