|
个人信息Personal Information
教授
博士生导师
硕士生导师
主要任职：Director of Academic Committee at Kaifa District
其他任职：开发区校区学术分委员会主任（Director of Academic Committee at Kaifa Campus）
性别：男
毕业院校：多伦多大学
学位：博士
所在单位：软件学院、国际信息与软件学院
学科：软件工程. 运筹学与控制论
办公地点：开发区（Kaifa District Campus）
联系方式：mingchul@dlut.edu.cn
电子邮箱：mingchul@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.