О нецелочисленных вершинах релаксаций многогранника задачи 3-ВЫПОЛНИМОСТЬ

Полный текст:


Аннотация

Устанавливаются новые факты, характеризующие множество вершин релаксационного многогранника задачи 3-ВЫПОЛНИМОСТЬ. В частности, рассмотрен вопрос о сохранении нецелочисленных вершин при переходе к более сильным релаксациям.

Об авторе

А. В. Николаев
Ярославский государственный университет им. П.Г. Демидова
Россия


Список литературы

1. Dantzig G. В., Fulkerson R., Johnson S. M. 'Solution of a large-scale traveling salesman problem // Operations Research. 1954. 2. P. 393-410.

2. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. 416 с.

3. Бондаренко В.А., Максименко А.Н. Геометрические конструкции и сложность в комбинаторной оптимизации. М.: ЛКИ, 2008. 184 с.

4. Деза М., Лоран М. Геометрия разрезов и метрик. М.: МЦНМО, 2001. 736 с.

5. Бондаренко В.А., Урываев Б.В. Об одной задаче целочисленной оптимизации // Автоматика и телемеханика. 2007. №6. С. 18-23.

6. Бондаренко В.А. Об одном комбинаторном многограннике // Моделирование и анализ вычислительных систем: Сб. науч. тр. Ярославль: Яросл. гос. ун-т., 1987. С. 133-134.

7. Padberg M.V. The Boolean quadratic polytope: some characteristics, facets and relatives // Mathematical Program. 1989. V. 45. P. 139-172.

8. Дунаева О.А., Николаев А.В. Некоторые свойства релаксационного многогранни¬ка задачи 3-выполнимость // Математическое моделирование и краевые задачи. Труды пятой Всероссийской научной конференции с международным участием. Самара: СамГТУ, 2008. С. 37-43.

9. PORTA: POlyhedron Representation Transformation Algorithm 1.4.0. Thomas Christof, Andreas Loebel. The Konrad-Zuse-Zentrum fur Informationstechnik Berlin, http://www.zib.de/Optimization/Software/Porta/


Дополнительные файлы

Для цитирования: Николаев А.В. О нецелочисленных вершинах релаксаций многогранника задачи 3-ВЫПОЛНИМОСТЬ. Моделирование и анализ информационных систем. 2010;17(2):99-111.

For citation: Nikolaev A.V. On nonintegral vertices of 3-SAT problem relaxation polytope. Modeling and Analysis of Information Systems. 2010;17(2):99-111. (In Russ.)

Просмотров: 25

Обратные ссылки

  • Обратные ссылки не определены.


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


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