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.