Ємець, ОлегЄмець, ЄлизаветаОльховський, Дмитро2013-03-072013-03-072011Ємець О. О. Оптимізаційні задачі на переставленнях: метод комбінаторного відсікання з використанням алгоритму Кармаркара / Ємець О. О., Ємець Є. М., Ольховський Д. М. // Наукові записки НаУКМА. - 2011. - Т. 125: Комп'ютерні науки. - С. 61-63.1996-5931https://ekmair.ukma.edu.ua/handle/123456789/2178Combinatorial optimization problems have been intensively researched in recent years, which lead to the development of new approaches and methods to solve these tasks. Important is the development of algorithms for solving combinatorial optimization. Method for solving combinatorial cut-off method of linear programming problems using Karmarkar’s algorithm is proposing in this paper. The article describes the method of combinatorial cut-off based on the Karmarkar algorithm. Formulated and proved a theorem about the finiteness of the proposed method.Останнім часом інтенсивно досліджуються задачі комбінаторної оптимізації, що призводить до розробки нових підходів та методів до їх розв’язування. Актуальною є розробка поліноміальних алгоритмів для розв’язування задач комбінаторної оптимізації. У цьому дослідженні запропоновано використовувати алгоритм Кармаркара у методі комбінаторного відсікання для розв’язування допоміжних задач лінійного програмування. Викладено метод комбінаторного відсікання на основі алгоритму Кармаркара. Сформульовано та доведено теорему про скінченність запропонованого методу.ukпереставленняметод комбінаторного відсіканняметод Кармаркараpermutationscombinatorial cut-off methodKarmarkar’s algorithmArticle