论文部分内容阅读
二次分配问题QAP（quadratic assignment problem）的变种问题是当前的研究热点．实际应用中存在一类不能用QAP及其现有变种描述的问题，该类问题在QAP问题的基础上增加了额外的约束条件：将设备分为黑白两色，其中白色设备要求与至少一个黑色设备的距离不超过预定阈值．文章将之定义为黑白二次分配问题BWQAP（Black and White QAP）．文章首先分析了它的计算复杂性，指出该问题是NP-难解问题，不存在ε-近似度的多项式时间近似算法（ε〉0）．同时证明了其可行解的存在性与黑白图