Hardprob/Minimum Hitting Set — различия между версиями

Текущая версия на 22:10, 17 апреля 2023

Коллекция C подмножеств конечного множества S.
Найти множество представителей (hitting set) для C, т.е. подмножество S' ⊆ S, такое, что S' содержит по крайней мере один элемент из каждого подмножества из C.
Минимизировать размер множества представителей, .

@@ Строка 2: / Строка 2: @@
 * Коллекция <em>C</em> подмножеств конечного множества <em>S</em>.
-* Найти множество представителей (hitting set) для <em>C</em>, т.е. подмножество <m>S'⊆ S</m>, такое, что <em>S'</em> содержит по крайней мере один элемент из каждого подмножества из <em>C</em>.
+* Найти множество представителей (hitting set) для <em>C</em>, т.е. подмножество <em>S' ⊆ S</em>, такое, что <em>S'</em> содержит по крайней мере один элемент из каждого подмножества из <em>C</em>.
 * Минимизировать размер множества представителей, <m>\vert S'| → \min</m>.