с учетом полуцелого решения LP из задачи о минимальном покрытии вершин с x € {0, 1/2, 1} Я ищу алгоритм, который возвращает целочисленное решение с x € {0,1}, котороеоптимальный.
Очевидно, что я не могу просто округлить все x, так как это приведет к слишком большому количеству вершин в минимальном наборе покрытия и, следовательно, не будет оптимальным.
Так что я должен решить, какие вершины с x = 1/2 должны быть 0, а какие должны быть 1.
Я думаю о том, чтобы посмотреть на соседей данной вершины с x =1/2, так что я могу решить, будет ли он в наборе или нет, но я думаю, что я что-то здесь упускаю.
Любые советы приветствуются:)