Том 17, номер 3, 2010 г., Стр. 19-31

УДК 519.8
Гимади Э. Х.
О вероятностном анализе приближённого алгоритма решения задачи о p-медиане

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

Ключевые слова: задача о p-медиане, приближённый алгоритм, асимптотическая точность, вероятность несрабатывания, теорема Петрова, равномерное распределение.

Гимади Эдуард Хайрутдинович ^1,2
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
2. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: gimadi@math.nsc.ru

Статья поступила 26 октября 2009 г.
Исправленный вариант — 27 декабря 2009 г.