Михайлюк В. А.
Реоптимизация задачи о максимальном k-покрытии: порог отношения аппроксимации

For any <$E epsilon ~>>~0> under an element inserted to or deleted from a set, the max k-cover problem cannot be reoptimized with the ratio of <$E 1~-~1 over {e~+~1} ~+~ epsilon> of unless <$E NP~symbol <171>~ TIME ( m sup {O( log log m )}>). A reoptimization algorithm with approximation ratio <$E 1~-~1 over {e~+~1}> is presented.

PDF