Не жадный алгоритм для Set Cover

Подробности о моих наборах: каждый набор имеет ровно M элементов, и каждый элемент принадлежит ровно N наборам.

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

есть хороший алгоритм? (для моего особого случая)

Благодарю.

1 ответ

Решение

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

Другие вопросы по тегам