|
个人信息Personal Information
教授
博士生导师
硕士生导师
主要任职：未来技术学院/人工智能学院副院长
性别：男
毕业院校：中国科技大学
学位：博士
所在单位：软件学院、国际信息与软件学院
联系方式：jianghe@dlut.edu.cn
扫描关注
Backbone of the p-median problem
点击次数：
论文类型：会议论文
发表时间：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.