虑软容量约束的动态设施选址问题. 假设设施的开放费用及连接费用都与时间有关, 而且每一个设施均有容量约束. 对此问题给出了第一个近似比为$6$的原始对偶(组合)算法. 运行贪婪增加程序后, 近似比进一步改进到$3.7052$.

The paper considers the soft-capacitated dynamic facility location problem (SCDFLP). It is assumed that the facility open cost and the connection cost are time-dependent, and each facility has a capacity. We present the first primal-dual (combinatorial) approximation algorithm for the problem with approximation ratio 6 . We further improve the approximation ration to 3.7052 using greedy augmentation scheme.