Approximation algorithms for multi-market competitive facility location problem with endogenous demand and diminishing marginal effect

Source: European Journal of Operational Research (2026)

Authors: Ling-Chieh Kung* (孔令傑), Ting-Hsu Chen (陳廷旭), Yuan-Ting Lin (林元婷)

URL: https://www.sciencedirect.com/science/article/pii/S0377221726004996

Abstract: We consider a profit-maximizing service provider’s competitive facility location problem where consumer demand is endogenously influenced by the construction plan. Moreover, the benefit of an open facility varies among different markets. While the demand of each market becomes higher when the total benefit from open facilities becomes higher, the marginal effect diminishes in the total benefit. With these characteristics, our multi-market facility location problem for profit maximization with endogenous demand can be formulated as a nonseparable nonlinear integer program. To obtain a near-optimal solution for this NP-hard problem, we propose approximation algorithms based on continuous relaxation and rounding incorporating a reduction on the number of fractional variables in an optimal solution. The procedure may be further simplified when there is only a single market. We derive the worst-case performance guarantees of our algorithms and show that it is the best among literature under certain conditions. Through numerical experiments, we demonstrate that the average-case performance of our algorithms is much better than the theoretical lower bounds.