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

Arie Tamir
Additional contact information
Arie Tamir: Tel Aviv University, Tel Aviv, Israel

Operations Research, 1998, vol. 46, issue 1, 157-158

Abstract: 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.

Keywords: Analysis of algorithms 011; heuristics 485; facility location 185 (search for similar items in EconPapers)
Date: 1998
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.46.1.157 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:46:y:1998:i:1:p:157-158

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().