Conditions for the effective solvability of the quadratic choice problem. Part 2

Authors

  • Vitaliy M. Demidenko Belarus State Economic University, 26 Partyzanski Avenue, Minsk 220070, Belarus

Keywords:

combinatorial optimisation, quadratic assignment problem, substitutions optimisation, strict solvability of problems
Supporting Agencies
Работа выполнена в рамках государственной программы научных исследований «Конвергенция-2025» (подпрограмма «Математические модели и методы», задание 1.5.01).

Abstract

In modern terminology, the conditions of the classical Hardy, Littlewood and Pólya theorem on the permutation of three systems guarantee the strict solvability of the optimisation problem for a bilinear form with a symmetric Toeplitz matrix of a special type. The bilinear form with the specified matrix takes extreme values on substitutions of two types, depending on whether the components of two vectors have the same or opposite orderings. Here the vectors determine the values of the variables of the bilinear form. The previous part of the article describes the conditions for achieving the minimum of the functional of the quadratic choice problem on the first of these substitutions. These conditions generalise all previously obtained results of a similar plan for the quadratic form minimisation problem and the quadratic assignment problem. This section of the paper considers conditions, imposing of which on the elements of a four-index matrix, guarantee the achievement of the minimum of the quadratic choice problem functional on the second substitution given in the three-system permutation theorem. The results presented in the two sections of the article describe by far the widest classes of four-index matrices for which the quadratic choice problem functional takes extreme values on fixed substitutions.

Author Biography

  • Vitaliy M. Demidenko, Belarus State Economic University, 26 Partyzanski Avenue, Minsk 220070, Belarus

    doctor of science (physics and mathematics), docent; professor at the department of higher mathematics, faculty of digital economics

References

  1. Koopmans TC, Beckmann M. Assignment problems and the location of economic activities. Econometrica. 1957;25(1):53–76. DOI: 10.2307/1907742.
  2. Hardy GH, Littlewood JE, Pólya G. The maximum of a certain bilinear form. Proceedings of the London Mathematical Society. 1926;25:265–282. DOI: 10.1112/plms/s2-25.1.265.
  3. Hardy GH, Littlewood JE, Pólya G. Inequalities. Cambridge: Cambridge University Press; 1934. XII, 314 p.
  4. Харди ГХ, Литлвуд ДжИ, Полиа Г. Неравенства. Левин ВИ, переводчик. Москва: Государственное издательство иностранной литературы; 1948. 456 с.
  5. Демиденко ВМ. Условия эффективной разрешимости квадратичной задачи выбора. Часть 1. Журнал Белорусского государственного университета. Математика. Информатика. 2024;1:45–58. EDN: TEYTMM.
  6. Бурков ВН, Рубинштейн МИ, Соколов ВБ. Некоторые задачи оптимального размещения информации в памяти большого объема. Автоматика и телемеханика. 1969;9:83–91.
  7. Тимофеев ББ, Литвинов ВА. К вопросу об организации размещения массивов информации в памяти на магнитных лентах. Кибернетика. 1969;4:56–61.
  8. Метельский НН. Об экстремальных значениях квадратичной формы на симметрической группе. Весцi Акадэмii навук БССР. Серыя фiзiка-матэматычных навук. 1972;6:107–110.
  9. Pratt VR. An N log N algorithm to distribute N records optimally in a sequential access file. In: Miller RE, Thatcher JW, editors. Complexity of computer computations. Proceedings of the symposium; 1972 March 20–22; New York, USA. New York: Plenum Press; 1972. p. 111–118 (The IBM research symposia series).
  10. Vickson RG, Lu X. Optimal product and server locations in one-dimensional storage racks. European Journal of Operational Research. 1998;105(1):18–28. DOI: 10.1016/S0377-2217(97)00023-4.
  11. Burkard RE, Çela E, Rote G, Woeginger GJ. The quadratic assignment problem with a monotone anti-Monge and a symmetric Toeplitz matrix: easy and hard cases. Mathematical Programming. 1998;82:125–158. DOI: 10.1007/BF01585868.
  12. Woeginger GJ. Computational problems without computation. Nieuw Archief voor Wiskunde. 2003;4(2):140–147.
  13. Woeginger GJ. Exact algorithms for NP-hard problems: a survey. In: Jünger M, Reinelt G, Rinaldi G, editors. Combinatorial optimization – eureka, you shrink! Revised papers of the 5th International workshop dedicated to Jack Edmonds; 2001 March 5–9; Aussois, France. Berlin: Springer; 2003. p. 185–207 (Goos G, Hartmanis J, van Leeuwen J, editors. Lecture notes in computer science; volume 2570). DOI: 10.1007/3-540-36478-1_17.
  14. Demidenko VM, Finke G, Gordon VS. Well solvable cases of the quadratic assignment problem with monotone and bimonotone matrices. Journal of Mathematical Modelling and Algorithms. 2006;5(2):167–187. DOI: 10.1007/s10852-005-9013-2.
  15. Демиденко ВМ. Квадратичная задача о назначениях с аддитивно монотонными матрицами и неполными матрицами анти-Монжа: условия эффективной разрешимости. Дискретная математика. 2007;19(1):105–132. EDN: HZFCZF.
  16. Demidenko VM, Dolgui A. Efficiently solvable cases of quadratic assignment problem with generalized monotonic and incomplete anti-Monge matrices. Cybernetics and Systems Analysis. 2007;43(1):112–125. DOI: 10.1007/s10559-007-0030-1.
  17. Çela E. Assignment problems. In: Pardalos PM, Resende MGC, editors. Handbook of applied optimization. Oxford: Oxford University Press; 2002. p. 661–678.
  18. Burkard R, Dell’Amico M, Martello S. Assignment problems. Philadelphia: Society for Industrial and Applied Mathematics; 2009. XX, 382 p.
  19. Демиденко ВМ. Эффективно разрешимые случаи и полиэдральные аспекты оптимизационных задач на подстановках [диссертация]. Минск: [б. и.]; 2011. 315 с.

Downloads

Published

2025-11-11

Issue

No. 2 (2025): Journal of the Belarusian State University. Mathematics and Informatics

Section

Discrete Mathematics and Mathematical Cybernetics

License

Copyright (c) 2025 Journal of the Belarusian State University. Mathematics and Informatics

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

The authors who are published in this journal agree to the following:

  1. The authors retain copyright on the work and provide the journal with the right of first publication of the work on condition of license Creative Commons Attribution-NonCommercial. 4.0 International (CC BY-NC 4.0).
  2. The authors retain the right to enter into certain contractual agreements relating to the non-exclusive distribution of the published version of the work (e.g. post it on the institutional repository, publication in the book), with the reference to its original publication in this journal.
  3. The authors have the right to post their work on the Internet (e.g. on the institutional store or personal website) prior to and during the review process, conducted by the journal, as this may lead to a productive discussion and a large number of references to this work. (See The Effect of Open Access.)

How to Cite

[1]
Demidenko, V.M. 2025. Conditions for the effective solvability of the quadratic choice problem. Part 2. Journal of the Belarusian State University. Mathematics and Informatics. 2 (Nov. 2025), 75–88. DOI:https://doi.org/10.33581/2520-6508-2025-2-75-88.