О вероятностном анализе приближённого алгоритма решения задачи о $p$-медиане

Для решения задачи размещения в так называемой $p$-медианной форме представлены приближённый алгоритм с временно́й сложностью $O(n^2)$ и результаты его вероятностного анализа. Входные данные определены на полном графе с расстояниями между вершинами – случайными независимыми переменными с одинаковой функцией равномерного распределения. Значение целевой функции, получаемой в результате работы алгоритма, представляет собой сумму случайных величин, анализ которых основан на оценке вероятностей больших уклонений этих сумм. В работе используется одна из предельных теорем такого анализа в форме неравенства Петрова, при этом учтён фактор зависимости суммируемых случайных величин. Результатом вероятностного анализа являются оценки относительной погрешности и вероятности несрабатывания представленного алгоритма, а также условия его асимптотической точности. Ил. 1, библиогр. 11.