Cybernetics And Systems Analysis logo
Editorial Board Announcements Abstracts Authors Archive
Cybernetics And Systems Analysis
International Theoretical Science Journal
UDC 519.168
O.M. Trofymchuk1, V.A. Vasyanin2


1 Institute of Telecommunication and Global Information Space of the National Academy of Sciences of Ukraine, Kyiv, Ukraine

itelua@kv.ukrtel.net

2 Institute of Telecommunication and Global Information Space of the National Academy of Sciences of Ukraine, Kyiv, Ukraine

archukr@meta.ua

CHOOSING THE CAPACITY OF ARCS WITH CONSTRAINT ON FLOW DELAY TIME

Abstract. The authors consider the problem of choosing the capacity arcs from a given set, which is important in flow distribution in multicommodity communication networks with constraint on flow delay time. It is proved that such problem is NP-hard. The algorithms for the approximate solution of the problem and results of heir experimental comparison with exact algorithm based on generating a sequence of binary reflected Gray codes are given. It is noted that obtaining an exact solution is possible with the use of pseudopolynomial algorithms for the 0–1 Multiple-choice Knapsack Problem.

Keywords: flows in networks, flow delay time, combinatorial optimization problems.



FULL TEXT

REFERENCES

  1. Kleinrock L. Queueuing systems. Vol. II: Computer applications. New York: John Wiley & Sons, 1976. 549 p.

  2. Bertsekas D., Gallager R. Data networks (2nd Ed.). Englewood Cliffs (N.J.): Prentice-Hall, Inc., 1992. 556 p.

  3. Zaichenko Yu.P. The problem of designing the structure of distributed computer networks. Avtomatika. 1981. N 4. P. 35–44.

  4. Zaichenko E.Yu. A complex of models and algorithms for optimizing the characteristics of networks with MPLS technology. Systems Analysis and Information Technology. 2007. N 4. P. 58–71.

  5. Trofymchuk O.M., Vasyanin V.A. Simulation of packing, distribution and routing of small-size discrete flows in a multicommodity network. Journal of Automation and Information Sciences. 2015. Vol. 47, Iss. 7. P. 15–30.

  6. Garey M.R., Johnson D.S. Computers and intractability: A guide to the theory of NP-completeness. New York: W.H. Freeman & Co., 1979. 338 p.

  7. Karp R.M. Reducibility among combinatorial problems. In: Complexity of computer computations. Miller R.E., Thatcher J.W. (Eds.). Proceedings of a symposium on the Complexity of Computer Computations. IBM Thomas J. Watson Research Center, Yorktown Heights. New York: Plenum Press, 1972. P. 85–103.

  8. Mikhalevich V.S., Shor N.Z. Numerical solutions of multivariate problems by the method of sequential analysis of options. Scientific and methodological materials of the economic and mathematical seminar. Moscow, 1962. Iss. 1. pp. 15–42. (Rotaprint of the AN SSSR; LEMI.)

  9. Mikhalevich V.S. Sequential optimization algorithms and their application. I. Kibernetika. 1965. N 1. С. 45–55; II. Ibid. N 2. С. 85–89.

  10. Volkovich V.L., Voloshin A.F. About one general scheme of sequential analysis and screening options. Kibernetika. 1978. N 5. P. 98–105.

  11. Mikhalevich V.S., Volkovich V.L., Voloshin A.F., Pozdnyakov Yu.M. Algorithms for sequential analysis and screening options in discrete optimization problems. Kibernetika. 1980. N 3. P. 76–85.

  12. Martelo S., Toth P. Knapsack problems: algorithms and computer implementations. Chichester: Wiley, 1990. 296 p.

  13. Kellerer H., Pferschy U., Pisinger D. Knapsack problems. Berlin; Heidelberg: Springer-Verlag, 2004. 548 p.

  14. Bansal M.S., Venkaiah V.Ch. Improved fully polynomial time approximation scheme for the 0–1 multiple-choice Knapsack pproblem. Technical Report Number: IIIT-H/TR/2004/003, IIIT, Hyderabad, India. 2004. 10 p.

  15. Suri B., Bordoloi U.D., Eles P. A scalable GPU-based approach to accelerate the multiple-choice knapsack problem. Design, Automation & Test in Europe Conference & Exhibition (DATE), 12–16 March 2012. Dresden: IEEE, 2012. 4 p. DOI: https://doi.org/10.1109/DATE.2012.6176665.

  16. Rhee D. Faster fully polynomial approximation schemes for Knapsack problems. Boston: Massachusetts Institute of Technology. Operations Research Center. 2015. 62 p. URL: http://hdl.handle.net/1721.1/98564.

  17. Bednarczuk E.M., Miroforidis J., Pyzel P. A multi-criteria approach to approximate solution of multiple-choice knapsack problem. Computational Optimization and Applications. 2018. Vol. 70, Iss. 3. P. 889–910.

  18. Bitner J.R., Ehrlich G., Reingold E.M. Efficient generation of the binary reflected Gray code and its applications. Comm. ACM. 1976. Vol. 19, Iss. 9. P. 517–521.

  19. Knuth D.E. The art of computer programming. Vol. 4A. Combinatorial algorithms. Part 1. Boston: Addison Wesley Longman, 2011. 933 p.

  20. Cerdeira J.O., Barcia P. When is a 0–1 knapsack a matroid? Portugaliae Mathematica. 1995. N 52. P. 475–480.
© 2019 Kibernetika.org. All rights reserved.