Том 18, номер 3, 2011 г., Стр. 76-83

УДК 519.85
Максименко А. Н.
Многогранники задачи о выполнимости являются гранями многогранника задачи коммивояжёра

Аннотация:
Пусть на множестве булевых переменных $U=\{u_1,u_2,\dots,u_d\}$ задана булева формула $C$ в конъюнктивной нормальной форме. Обозначим через $Y\subset\mathbb R^d$ множество характеристических векторов всех выполняющих $C$ наборов значений переменных. Многогранником задачи о выполнимости $S(U,C)$ назовём выпуклую оболочку множества $Y$. Многогранник коммивояжёра для орграфа на $n$ вершинах обозначим через $T_n$. Показано, что $S(U,C)$ аффинно эквивалентен некоторой грани многогранника $T_n$, где $n=|U|+2\operatorname{len}(C)$, $\operatorname{len}(C)$ – длина формулы $C$ в литералах.
Ил. 1, библиогр. 9.

Ключевые слова: многогранник коммивояжёра, многогранник задачи о выполнимости, грань.

Максименко Александр Николаевич ¹
1. Ярославский гос. университет им. П. Г. Демидова,
ул. Союзная, 144, 150008 Ярославль, Россия
е-mail: maksimenko_a_n@mail.ru

Статья поступила 19 июля 2010 г.
Исправленный вариант — 15 марта 2011 г.

Литература

[1] Бондаренко В. А. Неполиномиальная нижняя оценка сложности задачи коммивояжёра в одном классе алгоритмов // Автоматика и телемеханика. — 1983. — № 9. — С. 45–50.

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

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

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

[5] Applegate D. L., Bixby R. E., Chvatal V., Cook W. J. The traveling salesman problem: a computational study. — Princeton: Princeton Univ. Press, 2006. — 606 p.

[6] Billera L. J., Sarangarajan A. All 0-1 polytopes are travelling salesman polytopes // Combinatorica. — 1996. — Vol. 16. — P. 175–188.

[7] Fiorini S. A combinatorial study of partial order polytopes // Eur. J. Comb. — 2003. — Vol. 24, N 2. — P. 149–159.

[8] Karp R. M., Papadimitriou C. H. On linear characterizations of combinatorial optimization problems // SIAM J. Computing. — 1982. — Vol. 11, N 4. — P. 620–632.

[9] Papadimitriou C. H. The adjacency relation on the traveling salesman polytope is NP-complete // Math. Program. — 1978. — Vol. 14, N 1. — P. 312–324.