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 fi for opening a facility and the facility capacity ai are given. For each vertex j in N the demand volume bj is known. For each edge e in E the cost ce 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{amax,B}), where B=∑bj is total demand, amax is the maximum facility capacity.

To reports list