Comments on the Paper: ‘Heuristic and Special Case Algorithms for Dispersion Problems’ by S. S. Ravi, D. J. Rosenkrantz, and G. K. Tayi

The paper discusses Max-Min Facility Dispersion (MMFD) and Max-Avg Facility Dispersion (MAFD) problems. These problems are the subject of a paper by Ravi et al. (1994). The results presented in that paper include a simple heuristic for MMFD which provides a performance guarantee of 1/2, and a similar heuristic for MAFD with a performance guarantee of 1/4. It is also proved there that obtaining a performance guarantee of more than 1/2 for MMFD is NP-hard. For the two-dimensional version of MAFD, Ravi et al.'s paper presents a heuristic with an asymptotic performance guarantee of 2/p. Further additional comments in this direction are given.