Facility Location: A Theoretical Approach for Flood Relief
DOI:
https://doi.org/10.26438/ijcse/v5i11.8389Keywords:
Facility location, Disaster management, Approximation algorithm, NP-Hardness, Dominating sets, Link failure model, Graph theory, HardnessAbstract
We present a theoretical approach to come up with an effective mechanism for flood relief in terms of facility location problem with certain constraints. Facility location problem is a well studied economical decision problem to locate limited facility on demand points to cover maximum demand. Let consider a facility network under link failure. The problem is to locate emergency response facilities on a network with links that are subject to a failure model, called vulnerability − based dependency. We address the MAX-EXP-COVER-R problem in the facility network subjects to VB-dependency failure model. The MAX-EXP-COVER-R problem is known to be NP-hard. Let the distance factor R is relaxed from MAX-EXP-COVER-R problem, then it becomes MAX-EXP-COVER problem. The MAX-EXP-COVER problem can be solved in linear time using greedy algorithm. The MAX-EXP-COVER problem is further reduced into an instance of full binary tree, and then run MAX-WT-K-LEAF-SUBTREE problem on the tree will outputs the solution for MAX-EXP-COVER problem. Let the distance factor R = 1, then MAX-EXP-COVER-R problem is equivalent to budgeted dominating set problem with budget k and the induced subgraph of the solution set is need not to be connected.
References
Gerard Cornuejols, Marshall L. Fisher, and George L. Nemhauser. “location of bank accounts to optimize float: An analytic study of exact and approximate algorithms.” Management Science, 23(8):789–810, 1977.
Michael R. Garey and David S. Johnson. “Computers and Intractability: A Guide to the Theory of NP-Completeness.” W.H. Freeman and Co., San Francisco, CA, 1979.
S. Guha and S. Khuller. “Approximation algorithms for connected dominating sets”, Algorithmica, 20(4):374–387, 1998.
Refael Hassin, R. Ravi, and F. Sibel Salman. “Tractable Cases of Facility Location on a Network with a Linear Reliability Order of Links”, pages 275–276. Springer Berlin Heidelberg, Berlin, Heidelberg, 2009.
Hervé Kerivin and A. Ridha Mahjoub. “Design of survivable networks: A survey”, Netw., 46(1):1–21, August 2005.
Samir Khuller, Manish Purohit, and Kanthi K. Sarpatwar. “Analyzing the optimal neighborhood: Algorithms for budgeted and partial connected dominating set problems”, In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’14, pages 1702–1713, Philadelphia, PA, USA, 2014. Society for Industrial and Applied Mathematics.
F Sibel Salman and Eda Yücel. “Emergency facility location under random network damage: Insights from the istanbul case”, Computers & Operations Research, 62:266–281, 2015.
Downloads
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution 4.0 International License.
Authors contributing to this journal agree to publish their articles under the Creative Commons Attribution 4.0 International License, allowing third parties to share their work (copy, distribute, transmit) and to adapt it, under the condition that the authors are given credit and that in the event of reuse or distribution, the terms of this license are made clear.
