Том 11, серия 2, номер 1, 2004 г., Стр. 3-10

УДК 517.95
А. А. Агеев
Алгоритмы с улучшенными оценками точности для задачи о покрытии множествами

Аннотация:
Рассматривается классическая задача о покрытии множествами: для заданного конечного множества $I$ и семейства его подмножеств $\{S_j\mid j\in J\}$ с приписанными неотрицательными весами $w_j$ требуется найти подсемейство $\{S_j\mid j\in J^*\}$ с минимальным суммарным весом среди всех подсемейств, объединение которых совпадает с $I$. В работе предлагаются алгоритмы с улучшенными оценками точности для некоторых NP-трудных частных случаев этой задачи.

Агеев А. А. ¹
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: ageev@math.nsc.ru

Статья поступила 5 января 2004 г.