Locating independent facilities with maximum weight: Greedy heuristics

Sohail S Chaudhry, S Thomas McCormick and I Douglas Moon

Omega, 1986, vol. 14, issue 5, 383-389

Abstract: The problem is to locate a maximum-weight set of facilities such that no two are closer than a given distance from each other. The unweighted version is equivalent to the maximum independent set problem in graph theory. This paper presents four greedy heuristics and shows that they all have bad worst-case behavior. Empirically, however, these heuristics perform quite well in the relatively large test problems generated randomly.

Date: 1986
References: Add references at CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/0305-0483(86)90079-4
Full text for ScienceDirect subscribers only

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:eee:jomega:v:14:y:1986:i:5:p:383-389

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

Access Statistics for this article

Omega is currently edited by B. Lev

More articles in Omega from Elsevier
Bibliographic data for series maintained by Catherine Liu ().