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.

Facility location, Disaster management, Approximation algorithm, NP-Hardness, Dominating sets, Link failure model, Graph theory, Hardness.

[1] 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.
[2] 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.
[3] S. Guha and S. Khuller. “Approximation algorithms for connected dominating sets”, Algorithmica, 20(4):374–387, 1998.
[4] 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.
[5] Hervé Kerivin and A. Ridha Mahjoub. “Design of survivable networks: A survey”, Netw., 46(1):1–21, August 2005.
[6] 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.
[7] 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.