### Gimadi E. Tsidulko O. Shtepa A.A.

## Improved exact algorithm for the Capacitated Facility Location Problem on a line graph

### Reporter: Shtepa A.A.

We study the Capacitated Facility Location Problem (CFLP). Let G = (V,E) be an undirected graph, where the set of vertices V consists of two disjoint sets: set M, |M|=m, of facility locations, and set N, |N|=n of clients. For each vertex i in M the cost f_{i} for opening a facility and the facility capacity a_{i} are given. For each vertex j in N the demand volume b_{j} is known. For each edge e in E the cost c_{e} of the transportation of the product unit along this edge is given. The problem is to place the facilities in a way that all the clients demand are served, constraints on the facility capacities are not violated, and the total cost of opening facilities and delivering the product is minimized. We present a pseudopolynomial-time algorithm with time-complexity O(mB) for the CFLP on a line graph, which is faster than the best known algorithm from [Mirchandani et. al, 1996] with time-complexity O(mB min{a_{max},B}), where B=∑b_{j} is total demand, a_{max} is the maximum facility capacity.

To reports list