О ВЕРОЯТНОСТНОМ АНАЛИЗЕ ПРИБЛИЖЕННОГО АЛГОРИТМА РЕШЕНИЯ ЗАДАЧИ О <i>ρ</i>-МЕДИАНЕ
Для решения задачи размещения в так называемой ?-медианной форме представлены приближенный алгоритм с временной сложностью O(n2) и результаты его вероятностного анализа. Входные данные определены на полном графе с расстояниями между вершинами - случайными независимыми переменными с одинаковой функцией равномерного распределения. Значение целевой функции, получаемой в результате работы алгоритма, представляет собой сумму случайных величин, анализ которых основан на оценке вероятностей больших уклонений этих сумм. В работе используется одна из предельных теорем такого анализа в форме неравенства Петрова, при этом учтен фактор зависимости суммируемых случайных величин. Результатом вероятностного анализа являются оценки относительной погрешности и вероятности несрабатывания представленного алгоритма, а также условия его асимптотической точности.