О нецелочисленных вершинах релаксаций многогранника задачи 3-ВЫПОЛНИМОСТЬ
Аннотация
Ключевые слова
MSC2020: 519.16
Список литературы
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.)