Abstract. For any ε>0 under an element inserted to or deleted from a set, the max k-cover problem cannot be reoptimized with the ratio of 1 – (1/(e + 1)) + ε of unless NP ⊄ TIME(^{O(log log m)}). A reoptimization algorithm with approximation ratio 1 – (1/(e + 1)) + ε is presented. Refs: 14 titles.

Keywords: reoptimization, r-approximation algorithm.