Hits:
Indexed by:会议论文
Date of Publication:2007-12-02
Included Journals:EI、CPCI-S
Volume:4830
Page Number:699-704
Key Words:p-median; computational complexity; backbone
Abstract:PMP is a well-known NP-hard problem with extensively wide applications in location science and clustering. In this paper, we presented computational complexity results about the backbone, the shared common parts of all the optimal solutions to the PMP. We showed that it is intractable to approximate the backbone of the PMP with any performance guarantee under the assumption that P # NP.