EST

Call for paper
April Edition 2017

International Journal of Applied Information Systems solicits high quality original research papers for the
March 15, 2017
April 2017 Edition of the journal.
The last date of research paper submission is
March 15, 2017
SUBMIT YOUR PAPER

Number 3

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

journal image
 Download
1298

Export

  • Pawan Tamta and Bhagwati Prasad Pande and H. S. Dhami 2013. 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=http://dx.doi.org/10.5120/ijais450870 
  • @article{10.5120/ijais2017451568,
author = {Pawan Tamta and Bhagwati Prasad Pande and 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 = {},
month = {February},
year = {2013},
issn = {},
pages = {25-29},
numpages = {},
url = {/archives/volume5/number3/427-0870},
doi = { 10.5120/ijais12-450870},
publisher = { xA9 2012 by IJAIS Journal},
address = {}
}

  • %1 450870
%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
%@ 
%V 5
%N 
%P 25-29
%D 2013
%I  xA9 2012 by IJAIS Journal

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, T. L. Magnanti and J. B. Orlin, Network Flows: Theory, Algorithms and Applications, Prentice Hall, Upper Saddle River (1993).
  2. Douglas. S. Altner, Ozlem Eegun and Nelson A Uhan, The Maximum Flow Network Interdiction Problem, valid inequlities, itregality gaps and approximability, Operations Research Letter 38 (2010),pp 33-38.
  3. N. Assimakopoulos, A network interdiction model for hospital infection control, Computers in Biology and Medicine 17 (1987), pp. 413–422.
  4. Bar-Noy, A. , Guha, S. , Naor, J. , and Schieber, B. (2001). Approximating the throughput of multiple machines in real-time scheduling. SIAM Journal on Computing, 31(2):331–352.
  5. L. Bingol, A Lagrangian heuristic for solving a network interdiction problem, Master's thesis, Naval Postgraduate School, 2001.
  6. Boyd, S. and Carr, R. (1999). A new bound for the ratio between the 2-matching problem and its linear programming relaxation. Mathematical Programming, Ser A, 86:499–514.
  7. G. G. Brown, M. W. Carlyle, J. Salmerón and R. K. Wood, Defending critical infrastructure, Interfaces 36 (2006), pp. 530–544.
  8. C. Burch, R. D. Carr, M. Marathe, C. A. Phillips and E. Sundberg, A decomposition-based pseudoapproximation algorithm for network flow inhibition. In: D. L. Woodruff, Editor, Network Interdiction and Stochastic Integer Programming, Kluwer Academic Press (2002), pp. 51–68.
  9. R. L. Church, M. P. Scaparra and R. S. Middleton, Identifying critical infrastructure: The median and covering facility interdiction problems, Annals of the Association of American Geographers 94 (2004), pp. 491–502.
  10. Ricardo. A. Collado, David Papp, Network Interdiction-Models, Applications, Unexplored Directions, Rutcor Research Report, RRR 4-2012, January 2012.
  11. K. J. Cormican, D. P. Morton and R. K. Wood, Stochastic network interdiction, Operations Research 46 (1998), pp. 184–197.
  12. D. Du and R. Chandrasekaran, The maximum residual flow problem: NP-hardness with two-arc destruction, Networks 50 (2007), pp. 181–182.
  13. Ford, L. R. and Fulkerson, D. R. (1962). Flows in Networks. Princeton University Press, Princeton, NJ.
  14. Ghare, P. M. , Montgomery, D. C. , and Turner, W. C. (1971). Optimal interdiction policy for a flow network. Naval Research Logistics Quarterly, 18:37–45.
  15. T. E. Harris, F. S. Ross, Fundamentals of a method for evaluating rail network capacities, Research Memorandum RM-1573, The RAND Corporation, Santa Monica, CA.
  16. Helmbold, R. L. (1971). A counter capacity network interdiction model. Technical Report R-611-PR, Rand Corporation, Santa Monica, CA.
  17. E. Israeli and R. K. Wood, Shortest-path network interdiction, Networks 40 (2002), pp. 97–111.
  18. U. Janjarassuk and J. T. Linderoth, Reformulation and sampling to solve a stochastic network interdiction problem, Networks 52 (2008), pp. 120–132.
  19. Krumke, S. O. , Noltemeier, H. , Ravi, S. S. , Marathe, M. V. , and Drangmeister, K. U. (1998). Modifying networks to obtain low cost subgraphs. Theoretical Computer Science, 203(1):91–121.
  20. C. Lim and J. C. Smith, Algorithms for discrete and continuous multicommodity flow network interdiction problems, IIE Transactions 39 (2007), pp. 15–26.
  21. [Marathe et al. , 1998] Marathe, M. V. , Ravi, R. , Sundaram, R. , Ravi, S. S. , Rosenkrantz, D. J. , and Hunt III, H. B. (1998). Bicriteria network design problems. Journal of Algorithms, 28(1):142–171.
  22. A. W. McMasters and T. M. Mustin, Optimal interdiction of a supply network, Naval Research Logistics Quarterly 17 (1970), pp. 261–268.
  23. Naor, J. and Schieber, B. (1997), Improved approximations for shallow-light spanning trees. In Proceedings of the 38th Annual IEEE Symposium on the Foundations of Computer Science, pages 536–541.
  24. Nemhauser, G. L. and Wolsey, L. A. (1988), Integer and Combinatorial Optimization, John Wiley & Sons.
  25. Pawan Tamta, Bhagwati Pande, H. S. Dhami International, Development of an Algorithm for All Type of Network Flow Problems, Journal of Computer Applications (0975 – 8887) Volume 42– No. 17, March 2012.
  26. C. A. Phillips, The network inhibition problem, in: Proceedings of the 25th Annual ACM Symposium on the Theory of Computing, 1993 pp. 776–785.
  27. H. D. Ratliff, G. T. Sicilia and S. H. Lubore, Finding the n most vital links in flow networks, Management Science 21 (1975), pp. 531–539.
  28. J. O. Royset and R. K. Wood, Solving the bi-objective maximum-flow network-interdiction problem, INFORMS Journal on Computing 19 (2007), pp. 175–184.
  29. Schrijver, A. (1986). Theory of Linear and Integer Programming. John Wiley & Sons.
  30. A. Schrijver, On the history of the transportation and the maximum flow problems, Mathematical Programming 91 (2002), pp. 437–445.
  31. Shahram Morowati-Shalilvand, Javad Mehri-Tekmeh, Finding Most Vital Links over Time in a Flow Network. International Journal of Optimization And Control: Theories and Applications (IJOCTA), 2(2012), pp. 173-186.
  32. Shmoys, D. (1997), Personal communication.
  33. Srinivasan, A. (1997), A constant-factor approximation algorithm for packet routing, and balancing local vs global criteria. In Proceedings of the 29th Annual ACM Symposium on the Theory of Computing, pages 636–643.
  34. A. Uygun, Network interdiction by Lagrangian relaxation and branch-and- bound, Master's thesis, Naval Postgraduate School, 2002.
  35. R. K. Wood, Deterministic network interdiction, Mathematical and Computer Modelling, 17 (1993), pp. 1–18.

Keywords

Index Terms

Computer Science
Information Sciences