Mixed covering of trees and the augmentation problem with odd diameter constraints

In this talk, we will outline a polynomial time algorithm for solving the problem of partial covering of trees with n1 balls of radius R1 and n2 balls of radius R2(R10 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.