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

Question

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

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

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

спасибо.

Answer 1

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