论文部分内容阅读
在组合优化问题中,设施选址问题是一个经典问题,由于该问题是NP-困难问题,对于该类问题一般设计近似算法进行求解.无容量设施选址问题(uncapacitatedfacility location problem,简记为UFLP)是运筹学的经典问题之一,在许多文献中被广泛研究.随着问题研究和实际应用中的一些约束条件,无容量设施选址问题衍生了一系列的变形问题.在线设施选址问题就是其中重要的一类. 在本文中,我们主要研究了在线设施选址问题的一种变形问题:线性开设费用的在线设施选址问题.这个问题是指设施的开设费用是它服务顾客的线性函数,并且每一个顾客都有一个到达时间,而这个到达时间在租赁设施之前是未知的.在本文中我们采用对偶拟合的技巧设计出该问题的在线算法,并且证明了算法的竞争比为4Hn,其中n为出现的顾客的个数.