On nonintegral vertices of 3-SAT problem relaxation polytope
Abstract
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.
Keywords
combinatorial optimization,
computational complexity theory,
polytopes,
face lattice,
linear programming
MSC2020: 519.16
About the Author
A. V. Nikolaev
Ярославский государственный университет им. П.Г. Демидова
Russian Federation
Russian Federation
References
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/
Review
For citations:
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.)
Views:
438
Email this article 