线性开设费用在线设施选址问题的算法研究

作者：魏露

来源：无线互联科技, 2019, 16(18): 111-112.

• 在线
• 设施选址
• 线性开设费用
• 竞争比

设施选址问题是组合优化问题的经典问题,是NP-困难问题,一般设计近似算法进行求解。文章研究的线性开设费用的在线设施选址问题是在线设施选址问题的变形问题。利用对偶拟合的技巧,给出了竞争比为4Hn的在线算法,其中n为出现的顾客个数。

• 单位
  数理学院; 安阳工学院