鲁棒动态设施选址问题的近似算法

Approximation Algorithm for the Robust Dynamic Facility Location Problem

设施选址问题是组合优化中重要问题之一。动态设施选址问题是传统设施选址问题的推广,其中度量空间中设施的开设费用和顾客的需求均随着时间的变化而变化。更多地,经典设施选址问题假设所有的顾客都需要被服务。在这个模型假设下,所有的顾客都需要服务。但事实上,有时为服务距离较远的顾客,需要单独开设设施,导致了资源的浪费。因此,在模型设置中,可以允许一些固定数目的顾客不被服务(带异常点的设施选址问题),此外也可以通过支付一些顾客的惩罚费用以达到不服务的目的(带惩罚的设施选址问题)。本文将综合以上两种鲁棒设置考虑同时带有异常点和惩罚的动态设施选址问题,通过原始-对偶框架得到近似比为3的近似算法。

The facility location problem is one of the important problems in combinatorial optimization.The dynamic facility location problem is a generalization of the classic facility location problem in which the open cost of the facilities and the demand of the clients change over time.Moreover,the classic facility location problem always assumes that all clients need to be served.A shortcoming of the model is that it does not consider a few very distant clients.To serve these clients,some facilities need to be open to serve them only.This is not good for using the facilities resource.Thus,in the setting of the model,it is allowable that a constant number of clients can be not served(which is called the facility location problem with outliers).On the other hand,it is also allowable to pay penalty cost for not serving some clients(which is called the facility location problem with penalties).In this paper,we combine the above robust setting to consider the facility location problem with penalties and outliers for which we propose a 3-approximation algorithm.