Не жадный алгоритм для Set Cover
Подробности о моих наборах: каждый набор имеет ровно M элементов, и каждый элемент принадлежит ровно N наборам.
Мне нужен не жадный алгоритм, чтобы вычислить размер минимального набора покрытия.
есть хороший алгоритм? (для моего особого случая)
Благодарю.
1 ответ
Решение
Результаты твердости и, вероятно, результаты неприемлемости (возможно, с худшей константой) применимы даже к вашему особому случаю. Используйте решатель для смешанных целочисленных программ, таких как GLPK.