On the similarity of combinatorial optimization and universality of the algorithms
Abstract
A property of similarity which takes place in combinatorics and combinatorial optimization is examined. The various signs, after which it is determined for problems, which belong to the different classes, are defined. The problems of combinatorial optimization, which are similar by the argument of objective function, and in combinatorics – by the method of formation and ordering of combinatorial configurations, are described. Due to this property their sets are generated by the same algorithm or its modification. It is shown that some combinatorial optimization problems, which belong to different classes are divided into similar subproblems that are solved by the same calculable scheme. The property of similarity, which is typical for this class of problems, determines their universality by which they are solved by the same method. A study and use of this property in the combinatorial optimization in the future will reduce the insoluble problems to the solvables.
References
Reyngol’d E., Nivergel’t YU., Deo N. Kombinatornyye algoritmy. Teoriya i praktika: per. s angl. — M.: Mir, 1980. — 476 s.
Lipskiy V. Kombinatorika dlya programmistov: per. s pol’sk. — M.: Mir, 1988. — 213 s.
Papadimitriu KH., Stayglits K. Kombinatornaya optimizatsiya. Аlgoritmy i slozhnost’: per. s angl. — M.: Mir, 1985. — 510 s.
Sergiyenko I.V., Kaspshitskaya M.F. Modeli i metody resheniya na EVM kombinatornykh zadach optimizatsii. — K.: Nauk. dumka, 1981. — 281 s.
Bellman R. Dinamicheskoye programmirovaniye: per. s angl. — M.: Izd-vo inostrannoy literatury, 1960. — 400 s.
Mikhalevich V.S. Posledovatel’nyye algoritmy optimizatsii i ikh primeneniye // Kibernetika. — 1965. — № 1. — S. 45–56; № 2. — S. 85–89.
Timofeyeva N.K. O sposobakh obrazovaniya argumenta tselevoy funktsii v zadachakh kombinatornoy optimizatsii // Kibernetika i sistemnyy analiz. — 2002. — № 6. — C. 96–103.
Tymofiyeva N.K. Teoretyko-chyslovi metody rozvyazannya zadach kombinatornoyi optymizatsiyi. Avtoref. dys. dokt. tekhn. nauk / In-t kibernetyky im. V.M. Hlushkova NAN Ukrayiny, Kyyiv. — 2007. — 32 s.
KHardi G.G., Littl’vud Dzh. E., Polia G. Neravenstva: per. s angl. — M.: Gos. iz-vo inostr. lit., 1948. — 456 s.
Timofeyeva N.K. Opredeleniye mnozhestva znacheniy tselevoy funktsii v zadachakh diskretnoy optimizatsii // Kibernetika i vychislitel’naya tekhnika. Slozhnyye sistemy upravleniya: Sb. nauch. tr. — K., 1998 . — Vyp. 120. — S. 37–43.
Vintsyuk T.K. Аnaliz, raspoznavaniye i interpretatsiya rechevykh signalov. — K.: Naukova dumka, 1987. — 262 s.
