文档介绍：An Approximation Algorithm for the Dynamic Facility Location Problem
Contents
1. Introduction - 2 -
Issue of P and NP - 2 -
UFLP - 3 -
DFLP - 4 -
ρ: the approximation ratio of the algorithm / performance guarantee - 4 -
2. Approximation Algorithms for the UFLP - 5 -
3. Linear Programming Relaxation for the DFLP - 6 -
4. Research on DFLP - 8 -
Approximation Algorithm - 8 -
Analysis of Algorithm - 9 -
5. Problems and Solutions - 11 -
Problems - 11 -
Solutions - 12 -
6. Conclusions - 12 -
7. Reference - 13 -
Introduction
For facility location problem, its original version we are presented with a set of possible warehouse locations and a set of customer locations. Our objective is to decide on which of these possible warehouse locations we want to actually build warehouses. Since maintaining a warehouse incurs high costs, we want to build as few as possible.
On the other hand, every customer prefers to be located as close to a warehouse as possible, since costs rise with the distance to the nearest warehouse. This means that we are looking for a placement of the warehouses that minimizes the sum of the costs caused by the customers and the warehouses.
Generally, a facility will serve for a long time after constructing, but the factors that influence site selection are changing, so we had a dynamic facility location problem (Dynamic Facility Location Problem (DFLP)). What we want to study is this problem.
First, I want to introduce several Professional terminology:
Issue of P and NP
First we explain the plexity briefly. The plexity of a program does not mean that it takes much time to solve the problem, it is that the length of program time needed to grow how fast when the problem scale expands. That is, for high speed data puter, the data processing efficiency of a particular quality of a program cannot be measured, but should look when the data size expands several hundred times, if time of program run is the sa