Как выполнить релаксацию целочисленного линейного программирования формулировки покрытия вершин графа?

Question

Я реализую алгоритмы оптимизации из алгоритмов кернелизации для задачи покрытия вершин: теория и эксперименты (PDF).

Я немного застрял в главе 2.3: Ядро с помощью линейного программирования.

Идея этого метода (в формулировке ILP) заключается в назначении веса X_u \in \left\{ 0,1 \right\} к каждой вершине u (также обозначается как v) входного графа G=\left\( V,E \right\) чтобы удовлетворить следующие ограничения:

• Минимизировать сумму весов \Sigma_uX_u
• удовлетворять X_u + X_v \geq 1 всякий раз, когда \left\{ u,v \right \} связаны ребром в графе.

Итак, в качестве вывода я получаю набор вершин, имеющих X_v 1 и остальное, имея X_v 0. В статье говорится, что релаксация основана на замене X_u \in \left \{ 0,1 \right \} от X_u \geq 0, ( С. Хуллер (PDF) указывает, что в этом случае X_u \in \left \{ 0,0.5,1 \right \}). Эта релаксация привела бы к наличию 3 групп вершин с весами 1, 0,5 и 0.

Моя проблема в том, что я не совсем уверен, как подойти к назначению веса.

Из того, что я смог понять, чтобы минимизировать сумму весов, было бы лучше (для каждого ребра) сначала сфокусироваться на вершинах с наивысшими градусами, а когда их вес уже больше нуля, добавить значение к вершине на второй конец анализируемого края.

Это приводит меня (правильно?) К ситуации, когда на самом деле X_v \in \left \{ 0,1 \right \} для каждой вершины в основной формулировке. Когда я думаю об ослаблении целочисленного ограничения, оно просто меняется на X_v \in \left \{ 0,0.5 \right \},

Какой недостаток в моей логике?

Как мне нужно приблизиться к релаксации, чтобы иметь вершины с весом 1 и 0, а также 0,5?

Answer 1

Как вы заметили, ограничение X_v in {0, 1/2, 1} не поддается формулировке как (дробная) линейная программа. Что здесь происходит, это то, что, если вы установите более слабое ограничение X_v >= 0тогда существует какое-то оптимальное решение, где X_v in {0, 1/2, 1} держит для всех vхотя в целом не каждое оптимальное решение обладает этим свойством. Раздел 6 статьи, которую вы связали, представляет алгоритм, который находит такое оптимальное решение для покрытия вершин LP.