点击次数：

论文类型： 会议论文

发表时间： 2007-12-02

收录刊物： EI、CPCI-S

卷号： 4830

页面范围： 699-704

关键字： p-median; computational complexity; backbone

摘要： 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.