StasFomin: Новая страница: «Для данного семейства подмножеств найти минимальное число элементов S таких, что для люб…»

2017-12-09T13:01:37Z

Новая страница: «Для данного семейства подмножеств найти минимальное число элементов S таких, что для люб…»

Новая страница

Для данного семейства подмножеств найти минимальное число элементов S таких, что для любого подмножества из данного семейства в нем найдется хотя бы один элемент из S (hitting set). Более формально:

<latex>
Дано:
\begin{itemize}
\item Множество $S={s_1, \ldots, s_n}$,
\item Набор $С$ из подмножеств $S_1, \dots, S_m$ над $S$.
\end{itemize}

Найти минимальное подмножество $S' \subseteq S$, такое,
что для каждого подмножества $S_j$, в ней есть хотя бы один элемент из него.
</latex>

Minimum Hitting Set - История изменений

StasFomin: Новая страница: «Для данного семейства подмножеств найти минимальное число элементов S таких, что для люб…»