An Approximation Algorithm For Dynamic Facility Location Problem With Penalties And Outliers

Facility location problem is a typical combinatorial optimization problem.Although the problem is simple in structure,it has quite wide application background,which has involved extensive research and practicality in many domains,especially for the Internet,regional planning,circuit arrangement as well as aviation scheduling.Facility location problem is NP-hard,so it can't be solved accurately in polynomial time when P?NP.Therefore,we generally use approximation algorithms to deal with this kind of problem.Since simple models can't describe the complex and changeable situations that we encounter in the real world,a large number of new models based on actual conditions have been proposed in succession and developed prosperously in recent years.In this article,we study the dynamic facility location problem with penalties and outliers.In this model,demands of customers and relevant costs change over time,and customers have the penalty fee.Meanwhile,the situation that some customers are not being served is allowed.Among them,dynamic means that the opening cost of facilities,the connecting cost between customers and facilities and the customers'demands vary over time.Penalty refers to the dilemma that some customers are too far away from the facilities which have been opened,but opening a new facility for these customers particularly will result in a waste of resources.Therefore,the decision-makers can choose not to serve these customers and make up for their loss by paying penalty cost.Outliers means that we allow customers not to be served in the whole model and there is no need to pay penalty cost.It is stipulated that the number of customers with outliers is no more than l.Dynamic facility location problem with penalties and outliers is closer to the practical application scenarios in life,and enhances the application value of the model simultaneously.In this thesis,first of all,we introduce the mathematical model of uncapacitated facility location problem and its classical primal-dual algorithm with constant approximation ratio of 3.Secondly,three types of single deformation problems are proposed respectively.Then,through combining three types of deformations,we give a linear programming model for the dynamic facility location problem with penalties and outliers and show its dual programming.Finally,the primal-dual technique is utilized in order to design an approximation algorithm,whose approximate ratio is 3,and we give the analysis of relevant approximation ratio.