Об аппроксимационной сложности задачи о минимальном комитете

Авторы: 
Журнал: 
Страница: 
78
УДК: 
519.6
Изучается комбинаторная задача о минимальном комитете. Известно, что эта задача является ΝΡ-трудной. В статье показано, что если справедливо условие ΝΡ∉ΤΙΜΕ(mO(log log m)), то для произвольного ε > 0 не существует приближенного алгоритма задачи M F S с точностью (1 — ε) ln m.
info_eng: 
The Minimal Committee combinatorial problem (MC) is studied. It's known that this problem is ΝΡ-hard. In this paper we show that unless  ΝΡ∉ΤΙΜΕ(mO(log log m)) there are no approximation algorithms for this problem with factor (1 — ε) ln m for every ε > 0 even when all sets used in it's formulation are finite. To prove this estimate we reduce to it a SET COVER problem for which the same result is known.