О некоторых эффективно разрешимых классах сетевой задачи размещения с ограничениями на пропускные способности коммуникаций

Результат исследования: Научные публикации в периодических изданияхстатьярецензирование

Аннотация

В работе исследуется задача размещения в сетях с ограниченными пропускными способностями коммуникаций, в которой требуется разместить предприятия в вершинах заданной сети так, чтобы с минимальными затратами единовременно удовлетворить спросы всех клиентов, находящихся в вершинах сети. Рассматриваются постановки задачи с делимыми спросами, где спрос клиента может быть удовлетворен несколькими предприятиями совместно, и неделимыми спросами, тогда спрос клиента должен быть целиком удовлетворен одним предприятием. В работе показано, что задача с неделимыми спросами NP-трудна, даже если заданная сеть является простым путем, и NP-трудна в сильном смысле, если сеть - дерево. Задача с делимыми спросами слабо NP-трудна на деревьях. Для этой задачи в работе предложен псевдополиномиальный алгоритм решения на графах с древесной шириной, ограниченной константой, а также представлен линейный алгоритм для случая, когда граф сети является простым путем.
Переведенное названиеOn some efficiently solvable classes of the network facility location problem with constraints on the capacities of communication lines
Язык оригиналарусский
Страницы (с-по)108-124
Число страниц17
ЖурналTrudy Instituta Matematiki i Mekhaniki UrO RAN
Том26
Номер выпуска2
DOI
СостояниеОпубликовано - 1 фев 2020

ГРНТИ

  • 27 МАТЕМАТИКА

Fingerprint Подробные сведения о темах исследования «О некоторых эффективно разрешимых классах сетевой задачи размещения с ограничениями на пропускные способности коммуникаций». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать