Том 4, серия 2, номер 2, 1997 г., Стр. 55-62
УДК 519.8
М. И. Свириденко
Приближенный алгоритм для решения динамической задачи о $p$-медиане на максимум
Аннотация:
Исследуется задача, являющаяся обобщением задачи о$p$ -медиане на максимум. Предлагается приближенный полиномиальный алгоритм решения задачи с гарантированной оценкой погрешности$1-e^{-1}$ . Алгоритм основан на вероятностном округлении оптимального решения задачи линейного программирования, которая является релаксацией целочисленной задачи.
Библиогр. 4.
Свириденко М. И. 1
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
Статья поступила 15 августа 1997 г.
