В. П. Ильев, С. Д. Ильева, А. А. Навроцкая, “Приближенное решение задачи о $p$-медиане на минимум”, Ж. вычисл. матем. и матем. физ., 2016, том 56, номер 9,страницы 1614

Эта публикация цитируется в 2 статьях

Приближенное решение задачи о $p$-медиане на минимум

В. П. Ильев^ab, С. Д. Ильева^b, А. А. Навроцкая^ab

^a 630090 Новосибирск, пр-т Акад. Коптюга, 4, Ин-т матем. СО РАН
^b 644077 Омск, пр-т Мира, 55А, Омский гос. ун-т

Аннотация: Рассматривается одна из версий задачи размещения производства, известная как задача о $p$-медиане на минимум, и ее обобщение — задача минимизации супермодулярной функции. Эти задачи являются NP-трудными, для их приближенного решения применяется градиентный алгоритм, представляющий собой дискретный аналог алгоритма наискорейшего спуска. В статье представлены априорные гарантированные оценки точности градиентного алгоритма для рассматриваемых задач. Как следствие получена гарантированная оценка точности для задачи о p-медиане на минимум в терминах матрицы производственно-транспортных затрат. Библ. 14.

Ключевые слова: комбинаторная оптимизация, $p$-медиана, супермодулярная функция, градиентный алгоритм, гарантированная оценка точности.

УДК: 519.8

Поступила в редакцию: 16.11.2015
Исправленный вариант: 16.02.2016

DOI: 10.7868/S0044466916090088