An Approximation Algorithm for a Competitive Facility Location Problem with Network Effects

When facilities are built to serve end consumers directly, it is natural that consumer demands are affected by the number of open facilities. Moreover, sometimes a facility becomes more attractive if other facilities around it are built. To capture these factors, in this study we construct a discrete location model for profit maximization with endogenous consumer demands and network effects. The effective demand is then a concave function of the sum of benefits of open facilities due to the diminishing marginal benefit effect. When the function is linear, we design a polynomial-time algorithm to find an optimal solution. When it is nonlinear, we show that the problem is NP-hard and develop an approximation algorithm based on demand function approximation, linear relaxation, decomposition, and sorting. It is demonstrated that the proposed algorithm has worst-case performance guarantees for some special cases of our problem. Numerical studies are conducted to demonstrate the average performance and general applicability of our algorithms.