УДК 519.168

ЗАДАЧА ВИБОРУ ПРОПУСКНИХ СПРОМОЖНОСТЕЙ ДУГ З ОБМЕЖЕННЯМ
НА ЧАС ЗАТРИМКИ ПОТОКІВ

Трофимчук Александр Николаевич,
чл.-кор. НАН Украины, профессор, доктор техн. наук, директор Института телекоммуникаций и глобального информационного пространства НАН Украины, Киев,  itelua@kv.ukrtel.net

Васянин Владимир Александрович,
доктор техн. наук, ведущий научный сотрудник Института телекоммуникаций и глобального информационного пространства НАН Украины, Киев,  archukr@meta.ua

СПИСОК ЛІТЕРАТУРИ

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. Зайченко Ю.П. Задача проектирования структуры распределенных вычислительных сетей. Автоматика. 1981. № 4. С. 35–44.


4. Зайченко Е.Ю. Комплекс моделей и алгоритмов оптимизации характеристик сетей с технологией MPLS. Системні дослідження та інформаційні технології. 2007. № 4. С. 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. Михалевич В.С., Шор Н.З. Численные решения многовариантных задач по методу последовательного анализа вариантов. Научно-методические материалы экономико-математического семинара. Москва, 1962. Вып. 1. С. 15–42. (Ротапринт АН СССР; ЛЭМИ.)


9. Михалевич В.С. Последовательные алгоритмы оптимизации и их применение. I. Кибернетика. 1965. № 1. С. 45–55; II. Там же. № 2. С. 85–89.


10. Волкович В.Л., Волошин А.Ф. Об одной общей схеме последовательного анализа и отсеивания вариантов. Кибернетика. 1978. № 5. С. 98–105.


11. Михалевич В.С., Волкович В.Л., Волошин А.Ф., Поздняков Ю.М. Алгоритмы последовательного анализа и отсеивания вариантов в задачах дискретной оптимизации. Кибернетика. 1980. № 3. С. 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.