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