An approximation algorithm for a competitive facility location problem with network effects
Journal
European Journal of Operational Research
Journal Volume
267
Journal Issue
1
Pages
176-186
Date Issued
2018
Author(s)
Liao, W.-H.
Abstract
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.
SDGs
Type
journal article
File(s)![Thumbnail Image]()
Loading...
Name
SSRN-id3163078.pdf
Size
404.53 KB
Format
Adobe PDF
Checksum
(MD5):387132a7770ef40537c3cc79e3ff2f39