CFP last date
15 May 2024
Call for Paper
June Edition
IJAIS solicits high quality original research papers for the upcoming June edition of the journal. The last date of research paper submission is 15 May 2024

Submit your paper
Know more
The week's pick
Responsive image
Analysis of ANN Training Algorithms for Hand Geometry-Based Access Control

Kazeem B. Adedeji Apena Waliu O. Adu Michael R.
Random Articles
Reseach Article

Reduction of Maximum Flow Network Interdiction Problem: Step towards the Polynomial Time Solutions

by Pawan Tamta, Bhagwati Prasad Pande, H. S. Dhami
journal cover thumbnail

International Journal of Applied Information Systems
Foundation of Computer Science (FCS), NY, USA
Volume 5 - Number 3
Year of Publication: 2013
Authors: Pawan Tamta, Bhagwati Prasad Pande, H. S. Dhami
10.5120/ijais12-450870

Pawan Tamta, Bhagwati Prasad Pande, H. S. Dhami . Reduction of Maximum Flow Network Interdiction Problem: Step towards the Polynomial Time Solutions. International Journal of Applied Information Systems. 5, 3 ( February 2013), 25-29. DOI=10.5120/ijais12-450870

@article{ 10.5120/ijais12-450870,
author = { Pawan Tamta, Bhagwati Prasad Pande, H. S. Dhami },
title = { Reduction of Maximum Flow Network Interdiction Problem: Step towards the Polynomial Time Solutions },
journal = { International Journal of Applied Information Systems },
issue_date = { February 2013 },
volume = { 5 },
number = { 3 },
month = { February },
year = { 2013 },
issn = { 2249-0868 },
pages = { 25-29 },
numpages = {9},
url = { https://www.ijais.org/archives/volume5/number3/427-0870/ },
doi = { 10.5120/ijais12-450870 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2023-07-05T17:59:12.768794+05:30
%A Pawan Tamta
%A Bhagwati Prasad Pande
%A H. S. Dhami
%T Reduction of Maximum Flow Network Interdiction Problem: Step towards the Polynomial Time Solutions
%J International Journal of Applied Information Systems
%@ 2249-0868
%V 5
%N 3
%P 25-29
%D 2013
%I Foundation of Computer Science (FCS), NY, USA
Abstract

In the present work an attempt is being made to reduce the Maximum Flow Network Interdiction Problem (MFNIP) in to the Subset Sum Problem so as to get some algorithms solvable in polynomial time. Previously developed algorithms are either applicable to some special cases of MFNIP or they do not have a constant performance guarantee. Our reduction has paved the way towards the development of fully polynomial time approximation schemes for Maximum Flow Network Interdiction Problem.

References
  1. R. K. Ahuja
  2. T. L. Magnanti and J. B. Orlin
  3. Network Flows: Theory
  4. Algorithms and Applications
  5. Prentice Hall
  6. Upper Saddle River (1993).
  7. Douglas. S. Altner
  8. Ozlem Eegun and Nelson A Uhan
  9. The Maximum Flow Network Interdiction Problem
  10. valid inequlities
  11. itregality gaps and approximability
  12. Operations Research Letter 38 (2010)
  13. pp 33-38.
  14. N. Assimakopoulos
  15. A network interdiction model for hospital infection control
  16. Computers in Biology and Medicine 17 (1987)
  17. pp. 413–422.
  18. Bar-Noy
  19. A.
  20. Guha
  21. S.
  22. Naor
  23. J.
  24. and Schieber
  25. B. (2001). Approximating the throughput of multiple machines in real-time scheduling. SIAM Journal on Computing
  26. 31(2):331–352.
  27. L. Bingol
  28. A Lagrangian heuristic for solving a network interdiction problem
  29. Master's thesis
  30. Naval Postgraduate School
  31. 2001.
  32. Boyd
  33. S. and Carr
  34. R. (1999). A new bound for the ratio between the 2-matching problem and its linear programming relaxation. Mathematical Programming
  35. Ser A
  36. 86:499–514.
  37. G. G. Brown
  38. M. W. Carlyle
  39. J. Salmerón and R. K. Wood
  40. Defending critical infrastructure
  41. Interfaces 36 (2006)
  42. pp. 530–544.
  43. C. Burch
  44. R. D. Carr
  45. M. Marathe
  46. C. A. Phillips and E. Sundberg
  47. A decomposition-based pseudoapproximation algorithm for network flow inhibition. In: D. L. Woodruff
  48. Editor
  49. Network Interdiction and Stochastic Integer Programming
  50. Kluwer Academic Press (2002)
  51. pp. 51–68.
  52. R. L. Church
  53. M. P. Scaparra and R. S. Middleton
  54. Identifying critical infrastructure: The median and covering facility interdiction problems
  55. Annals of the Association of American Geographers 94 (2004)
  56. pp. 491–502.
  57. Ricardo. A. Collado
  58. David Papp
  59. Network Interdiction-Models
  60. Applications
  61. Unexplored Directions
  62. Rutcor Research Report
  63. RRR 4-2012
  64. January 2012.
  65. K. J. Cormican
  66. D. P. Morton and R. K. Wood
  67. Stochastic network interdiction
  68. Operations Research 46 (1998)
  69. pp. 184–197.
  70. D. Du and R. Chandrasekaran
  71. The maximum residual flow problem: NP-hardness with two-arc destruction
  72. Networks 50 (2007)
  73. pp. 181–182.
  74. Ford
  75. L. R. and Fulkerson
  76. D. R. (1962). Flows in Networks. Princeton University Press
  77. Princeton
  78. NJ.
  79. Ghare
  80. P. M.
  81. Montgomery
  82. D. C.
  83. and Turner
  84. W. C. (1971). Optimal interdiction policy for a flow network. Naval Research Logistics Quarterly
  85. 18:37–45.
  86. T. E. Harris
  87. F. S. Ross
  88. Fundamentals of a method for evaluating rail network capacities
  89. Research Memorandum RM-1573
  90. The RAND Corporation
  91. Santa Monica
  92. CA.
  93. Helmbold
  94. R. L. (1971). A counter capacity network interdiction model. Technical Report R-611-PR
  95. Rand Corporation
  96. Santa Monica
  97. CA.
  98. E. Israeli and R. K. Wood
  99. Shortest-path network interdiction
  100. Networks 40 (2002)
  101. pp. 97–111.
  102. U. Janjarassuk and J. T. Linderoth
  103. Reformulation and sampling to solve a stochastic network interdiction problem
  104. Networks 52 (2008)
  105. pp. 120–132.
  106. Krumke
  107. S. O.
  108. Noltemeier
  109. H.
  110. Ravi
  111. S. S.
  112. Marathe
  113. M. V.
  114. and Drangmeister
  115. K. U. (1998). Modifying networks to obtain low cost subgraphs. Theoretical Computer Science
  116. 203(1):91–121.
  117. C. Lim and J. C. Smith
  118. Algorithms for discrete and continuous multicommodity flow network interdiction problems
  119. IIE Transactions 39 (2007)
  120. pp. 15–26.
  121. [Marathe et al.
  122. 1998] Marathe
  123. M. V.
  124. Ravi
  125. R.
  126. Sundaram
  127. R.
  128. Ravi
  129. S. S.
  130. Rosenkrantz
  131. D. J.
  132. and Hunt III
  133. H. B. (1998). Bicriteria network design problems. Journal of Algorithms
  134. 28(1):142–171.
  135. A. W. McMasters and T. M. Mustin
  136. Optimal interdiction of a supply network
  137. Naval Research Logistics Quarterly 17 (1970)
  138. pp. 261–268.
  139. Naor
  140. J. and Schieber
  141. B. (1997)
  142. Improved approximations for shallow-light spanning trees. In Proceedings of the 38th Annual IEEE Symposium on the Foundations of Computer Science
  143. pages 536–541.
  144. Nemhauser
  145. G. L. and Wolsey
  146. L. A. (1988)
  147. Integer and Combinatorial Optimization
  148. John Wiley & Sons.
  149. Pawan Tamta
  150. Bhagwati Pande
  151. H. S. Dhami International
  152. Development of an Algorithm for All Type of Network Flow Problems
  153. Journal of Computer Applications (0975 – 8887) Volume 42– No. 17
  154. March 2012.
  155. C. A. Phillips
  156. The network inhibition problem
  157. in: Proceedings of the 25th Annual ACM Symposium on the Theory of Computing
  158. 1993 pp. 776–785.
  159. H. D. Ratliff
  160. G. T. Sicilia and S. H. Lubore
  161. Finding the n most vital links in flow networks
  162. Management Science 21 (1975)
  163. pp. 531–539.
  164. J. O. Royset and R. K. Wood
  165. Solving the bi-objective maximum-flow network-interdiction problem
  166. INFORMS Journal on Computing 19 (2007)
  167. pp. 175–184.
  168. Schrijver
  169. A. (1986). Theory of Linear and Integer Programming. John Wiley & Sons.
  170. A. Schrijver
  171. On the history of the transportation and the maximum flow problems
  172. Mathematical Programming 91 (2002)
  173. pp. 437–445.
  174. Shahram Morowati-Shalilvand
  175. Javad Mehri-Tekmeh
  176. Finding Most Vital Links over Time in a Flow Network. International Journal of Optimization And Control: Theories and Applications (IJOCTA)
  177. 2(2012)
  178. pp. 173-186.
  179. Shmoys
  180. D. (1997)
  181. Personal communication.
  182. Srinivasan
  183. A. (1997)
  184. A constant-factor approximation algorithm for packet routing
  185. and balancing local vs global criteria. In Proceedings of the 29th Annual ACM Symposium on the Theory of Computing
  186. pages 636–643.
  187. A. Uygun
  188. Network interdiction by Lagrangian relaxation and branch-and- bound
  189. Master's thesis
  190. Naval Postgraduate School
  191. 2002.
  192. R. K. Wood
  193. Deterministic network interdiction
  194. Mathematical and Computer Modelling
  195. 17 (1993)
  196. pp. 1–18.
Index Terms

Computer Science
Information Sciences

Keywords

Maximum Flow Network Interdiction Polynomial Time Solutions MFNIP Subset Sum Problem polynomial

Powered by PhDFocusTM