Минимальный алгоритм крышки вершины с линейным программированием

Question

Рассмотрим следующий алгоритм: учитывая график $ g $ с $ n $ вершины, настройки Линейная проблема программирования LP , где есть переменная $ x_i $ для каждой вершины $ v_i $ of $ G $ , каждая переменная может принимать значение $ \ geq 0 $ , для каждого Edge $ v_av_b $ $ G $ Установите ограничение $ x_a + x_b \ geq 1 $ . Объективная функция - $ \ min \ sum \ limits_ {1} ^ {n} {x_i} $ . Найдите переменную (или одну из переменных) $ x_i $ , среди переменных, не установленных на $ 0 $ , что установлено на $ 0 $ дает минимальное значение объективной функции. Добавьте ограничение $ x_i= 0 $ на lp . Повторите до тех пор, пока оптимальный раствор LP LP не является целым числом (то есть каждая переменная имеет значение в $ \ Left \ {0; 1 \ Right \} $ ).

Я ищу график, в котором вершины, связанные с переменными, которые принимают значение $ 1 $ в конечном оптимальном решении LP Не минимальная крышка вершины $ g $ (если он существует).

Answer 1

Рассмотрим график

  2-4---7
 /  |\ /|
1   | × |
 \  |/ \|
  3-5---6

.

Настройка $ x_1, x_2, x_3, x_6 $ или $ x_7 $ до 0 дает ваш lpЗначение 4, при настройке $ x_4 $ или $ x_5 $ до 0 дает ваше значение LP5. Однако, если вы устанавливаете $ x_1= 0 $ , вы, наконец, получите крышку вершины 5, а оптимальная крышка вершины имеет размер 4.

.