An approximation algorithm for a competitive facility location problem with network effects

Ling-Chieh Kung and Wei-Hung Liao

European Journal of Operational Research, 2018, vol. 267, issue 1, 176-186

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.

Keywords: Location; Competitive facility location problem; Network effect; Approximation algorithm (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221717310482
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:267:y:2018:i:1:p:176-186

DOI: 10.1016/j.ejor.2017.11.037

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().