Подход к оценке сложности в среднем постоптимального анализа дискретных задач оптимизации

Михайлюк, В. А.

Михайлюк В. А.
Подход к оценке сложности в среднем постоптимального анализа дискретных задач оптимизации / В. А. Михайлюк // Кибернетика и системный анализ. - 2011. - Т. 47, № 6. - С. 47-58. - Режим доступу: http://nbuv.gov.ua/UJRN/KSA_2011_47_6_6

It is shown that a ZPP-, RP-probabilistic polynomial procedures of postoptimality analysis for finding the optimal solution of a set cover problem that differs from the original problem in one position of matrix of constraints do not exist if the optimal solution of the original problem is known and if <$E ZPP ~ symbol Щ ~NP ~(RP~ symbol Щ ~NP)>. A similar result holds for the knapsack problem.It is shown that an algorithm polynomial on the average with respect to to calculate the optimal solution of the set cover problem that differs from the original problem in one position of the constraint matrix doesn't exist if the optimal solution of the original problem is known and unless DistNP <$E symbol <173>> Average-P. A similar result is true for the knapsack problem.

Повний текст PDF - 137.841 Kb Зміст випуску Цитування публікації

Цитованість авторів публікації:
Михайлюк В.

Бібліографічний опис для цитування:
Михайлюк В. А. Подход к оценке сложности в среднем постоптимального анализа дискретных задач оптимизации / В. А. Михайлюк // Кибернетика и системный анализ. - 2011. - Т. 47, № 6. - С. 47-58. - Режим доступу: http://nbuv.gov.ua/UJRN/KSA_2011_47_6_6.
Якщо, ви не знайшли інформацію про автора(ів) публікації, маєте бажання виправити або відобразити більш докладну інформацію про науковців України запрошуємо заповнити "Анкету науковця"

Відділ інформаційно-комунікаційних технологій

Пам`ятка користувача


	Наукова періодика України		Кібернетика та системний аналіз