Methods of reduction of insolvable problems of combinatorial optimization to solvable problems
Keywords:
subclasses of solvable problem, function of natural argument, combinatorial function, combinatorial optimization, the complexity of the tasks, objective function, combinatorial configurationAbstract
For the selection of subclasses of solvable problems from the classes of unsolvable ones the necessity to determine their complexity is shown in the article. On this basis the classification of solvable problems, which are allocated by the selected similarity degree and the way of modeling the objective function, according to the structure of the input data and the structure of its argument is carried out. On the example of some classes of unsolvable problems of combinatorial optimization methods their attempts to make them solvable are described.References
1. Дейнеко В. Г. Розв’язність в комбінаторній оптимізації. Розв’язні випадки проблеми комівояжера та еврістичні алгоритми : автореф. дис. на здобуття наук. ступеня докт. фіз.мат.. наук: 01.05.01 / В. Г. Дейнеко. — Ін-т кібернетики ім. В. М. Глушкова НАН України. — К., 1995. — 48 с.
2. Демиденко В. М. Об экстремальных задачах на подстановках : автореф. дис. на здобуття наук. ступеня канд. физ.-мат. наук: 01.01.09 / В. М. Демиденко. — Ин-т математики АН БССР. — Минск, 1980. — 14 с.
3. Тимофієва Н. К. Теоретико-числові методи розв’язання задач комбінаторної оптимізації : автореф. дис. на здобуття наук. ступеня докт. техн. наук / Н. К. Тимофієва. — Ін-т кібернетики ім. В. М. Глушкова НАН України, Київ. — 2007. — 32 с.
4. Пападимитриу Х. Комбинаторная оптимизация. Алгоритмы и сложность / Х. Пападимитриу, К. Стайглиц ; пер. с англ. — М. : Мир, 1985. — 510 с.
5. Сергиенко И. В. Модели и методы решения на ЭВМ комбинаторных задач оптимизации / И. В. Сергиенко,
М. Ф. Каспшицкая. — К. : Наук. думка, 1981. — 281 с.
6. Корбут А. А. Дискретное программирование / А. А. Корбут, Ю. Ю. Финкельштейн. — М. : Наука, 1969. — 368 с.
7. Михалевич В. С. Оптимизационные задачи производственно-транспортного планирования / В. С. Михалевич,
В. А. Трубин, Н. З. Шор. — М. : Наука, 1986. — 264 с.
8. Тимофеева Н. К. О некоторых свойствах разбиений множества на подмножества / Н. К. Тимофеева // УСиМ. — 2002. — № 5. — С. 6—23.
9. Тимофеева Н. К. Зависимость целевой функции задач комбинаторной оптимизации от упорядочения комбинаторных конфигураций / Н. К. Тимофеева // Компьютерная математика : сб. науч. тр. — 2005. — № 2. — С. 135—146.
10. Тимофієва Н. К. Метод структурно-алфавітного пошуку та підкласи розв’язних задач із класу задачі комівояжера / Н. К. Тимофієва // УСиМ — 2008. — № 4 — С. 20—36.
2. Демиденко В. М. Об экстремальных задачах на подстановках : автореф. дис. на здобуття наук. ступеня канд. физ.-мат. наук: 01.01.09 / В. М. Демиденко. — Ин-т математики АН БССР. — Минск, 1980. — 14 с.
3. Тимофієва Н. К. Теоретико-числові методи розв’язання задач комбінаторної оптимізації : автореф. дис. на здобуття наук. ступеня докт. техн. наук / Н. К. Тимофієва. — Ін-т кібернетики ім. В. М. Глушкова НАН України, Київ. — 2007. — 32 с.
4. Пападимитриу Х. Комбинаторная оптимизация. Алгоритмы и сложность / Х. Пападимитриу, К. Стайглиц ; пер. с англ. — М. : Мир, 1985. — 510 с.
5. Сергиенко И. В. Модели и методы решения на ЭВМ комбинаторных задач оптимизации / И. В. Сергиенко,
М. Ф. Каспшицкая. — К. : Наук. думка, 1981. — 281 с.
6. Корбут А. А. Дискретное программирование / А. А. Корбут, Ю. Ю. Финкельштейн. — М. : Наука, 1969. — 368 с.
7. Михалевич В. С. Оптимизационные задачи производственно-транспортного планирования / В. С. Михалевич,
В. А. Трубин, Н. З. Шор. — М. : Наука, 1986. — 264 с.
8. Тимофеева Н. К. О некоторых свойствах разбиений множества на подмножества / Н. К. Тимофеева // УСиМ. — 2002. — № 5. — С. 6—23.
9. Тимофеева Н. К. Зависимость целевой функции задач комбинаторной оптимизации от упорядочения комбинаторных конфигураций / Н. К. Тимофеева // Компьютерная математика : сб. науч. тр. — 2005. — № 2. — С. 135—146.
10. Тимофієва Н. К. Метод структурно-алфавітного пошуку та підкласи розв’язних задач із класу задачі комівояжера / Н. К. Тимофієва // УСиМ — 2008. — № 4 — С. 20—36.
Downloads
-
PDF (Українська)
Downloads: 63
Abstract views: 106
Published
2010-11-12
How to Cite
[1]
N. K. Tymofiieva, “Methods of reduction of insolvable problems of combinatorial optimization to solvable problems”, Вісник ВПІ, no. 3, pp. 240–244, Nov. 2010.
Issue
Section
Fundamental sciences
License
Authors who publish with this journal agree to the following terms:
- Authors retain copyright and grant the journal right of first publication.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgment of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
