4817
правок
Максимальный разрез: различия между версиями
Материал из WEGA
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 50: | Строка 50: | ||
'''Полуопределенная релаксация''' | '''Полуопределенная релаксация''' | ||
Задачу MAX-CUT можно сформулировать в виде следующей квадратичной целочисленной программы, решение которой является NP-трудным. Каждая вершина i | Задачу MAX-CUT можно сформулировать в виде следующей квадратичной целочисленной программы, решение которой является NP-трудным. Каждая вершина <math>i \in V</math> представлена переменной <math>y_i</math>, которой присваивается значение 1 либо -1 в зависимости от того, с какой стороны от разреза она располагается. | ||
<math>max \frac{1}{2} \sum_{(i, j) \in E} w_{ij} (1 - y_i y_j)</math> | |||
<math>y_i \in \{ -1, 1 \} \; \; \forall i \in E</math>. | |||
Гёманс и Уильямсон рассмотрели следующую релаксацию этой целочисленной программы, в которой каждая вершина представлена единичным вектором. | Гёманс и Уильямсон рассмотрели следующую релаксацию этой целочисленной программы, в которой каждая вершина представлена единичным вектором. | ||
<math>max \frac{1}{2} \sum_{(i, j) \in E} w_{ij} (1 - v_i \cdot v_j)</math> | |||
<math>v_i \cdot v_i = 1 \; \; \forall i \in V</math> | |||
<math>v_i \in \mathcal{R}^n \; \; \forall i \in V</math>. | |||
Они показали, что данная релаксация эквивалентна полуопределенной программе. Рассмотрим следующую полуопределенную релаксацию: | Они показали, что данная релаксация эквивалентна полуопределенной программе. Рассмотрим следующую полуопределенную релаксацию: | ||
<math>max \frac{1}{2} \sum_{(i, j) \in E} w_{ij} (1 - y_{ij})</math> | |||
<math>y_{ii} = 1 \; \; \forall i \in V</math> | |||
Y – положительно полуопределенная матрица. | |||
