Mixed Covering of Trees and the Augmentation Problem with Odd Diameter Constraints

In this paper we present a polynomial time algorithm for solving the problem of partial covering of trees with n₁ balls of radius R₁ and n₂ balls of radius R₂ (R₁ < R₂) to maximize the total number of covered vertices. The solutions provided by this algorithm in the particular case R₁ = R – 1, R₂ = R can be used to obtain for any integer δ > 0 a factor (2+1/δ) approximation algorithm for solving the following augmentation problem with odd diameter constraints D = 2R + 1: Given a tree T, add a minimum number of new edges such that the augmented graph has diameter ≤ D. The previous approximation algorithm of Ishii, Yamamoto, and Nagamochi (2003) has factor 8.