论文部分内容阅读
本文讨论k-层软容量设施选址博弈,它是k-层软容量设施选址问题的变形.众所周知,设施选址问题是NP-难问题,做为设施选址问题的推广,k-层软容量设施选址问题也是NP-难问题.除非P=NP,我们不能在多项式时间内给出k-层软容量设施选址问题的最优解.
k-层软容量设施选址博弈是1-层设施选址博弈的推广.本文给出k-层软容量设施选址博弈的第一个费用分摊算法.利用原始-对偶技巧,我们得到了满足单调性、竞争性和12-近似补偿的费用分摊算法.