Приближенный алгоритм для решения динамической задачи о $p$-медиане на максимум

Исследуется задача, являющаяся обобщением задачи о $p$-медиане на максимум. Предлагается приближенный полиномиальный алгоритм решения задачи с гарантированной оценкой погрешности $1-e^{-1}$. Алгоритм основан на вероятностном округлении оптимального решения задачи линейного программирования, которая является релаксацией целочисленной задачи.
Библиогр. 4