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

Версия 11:08, 17 апреля 2023

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

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