On nonintegral vertices of 3-SAT problem relaxation polytope
New facts characterizing the vertex set of 3-SAT problem relaxation polytope are established. In particular, the question of preservation of nonintegral vertices under additional linear constraints of stronger relaxations is examined.
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Yaroslavl State University
2010-06-01
|
| Series: | Моделирование и анализ информационных систем |
| Subjects: | |
| Online Access: | https://www.mais-journal.ru/jour/article/view/1031 |
| _version_ | 1797877931716902912 |
|---|---|
| author | A. V. Nikolaev |
| author_facet | A. V. Nikolaev |
| author_sort | A. V. Nikolaev |
| collection | DOAJ |
| description | New facts characterizing the vertex set of 3-SAT problem relaxation polytope are established. In particular, the question of preservation of nonintegral vertices under additional linear constraints of stronger relaxations is examined. |
| first_indexed | 2024-04-10T02:25:47Z |
| format | Article |
| id | doaj.art-2695dbaa88984141b9320917b3c1adc0 |
| institution | Directory Open Access Journal |
| issn | 1818-1015 2313-5417 |
| language | English |
| last_indexed | 2024-04-10T02:25:47Z |
| publishDate | 2010-06-01 |
| publisher | Yaroslavl State University |
| record_format | Article |
| series | Моделирование и анализ информационных систем |
| spelling | doaj.art-2695dbaa88984141b9320917b3c1adc02023-03-13T08:07:31ZengYaroslavl State UniversityМоделирование и анализ информационных систем1818-10152313-54172010-06-0117299111772On nonintegral vertices of 3-SAT problem relaxation polytopeA. V. Nikolaev0Ярославский государственный университет им. П.Г. ДемидоваNew facts characterizing the vertex set of 3-SAT problem relaxation polytope are established. In particular, the question of preservation of nonintegral vertices under additional linear constraints of stronger relaxations is examined.https://www.mais-journal.ru/jour/article/view/1031комбинаторная оптимизациятеория сложностимногогранникиграничные комплексызадача линейного программирования |
| spellingShingle | A. V. Nikolaev On nonintegral vertices of 3-SAT problem relaxation polytope Моделирование и анализ информационных систем комбинаторная оптимизация теория сложности многогранники граничные комплексы задача линейного программирования |
| title | On nonintegral vertices of 3-SAT problem relaxation polytope |
| title_full | On nonintegral vertices of 3-SAT problem relaxation polytope |
| title_fullStr | On nonintegral vertices of 3-SAT problem relaxation polytope |
| title_full_unstemmed | On nonintegral vertices of 3-SAT problem relaxation polytope |
| title_short | On nonintegral vertices of 3-SAT problem relaxation polytope |
| title_sort | on nonintegral vertices of 3 sat problem relaxation polytope |
| topic | комбинаторная оптимизация теория сложности многогранники граничные комплексы задача линейного программирования |
| url | https://www.mais-journal.ru/jour/article/view/1031 |
| work_keys_str_mv | AT avnikolaev onnonintegralverticesof3satproblemrelaxationpolytope |