Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
О некоторых эффективно разрешимых классах сетевой задачи размещения с ограничениями на пропускные способности коммуникаций. / Gimadi, Edward Khairutdinovich; Tsidulko, Oxana Yurievna.
в: Trudy Instituta Matematiki i Mekhaniki UrO RAN, Том 26, № 2, 25.05.2020, стр. 108-124.Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
}
TY - JOUR
T1 - О некоторых эффективно разрешимых классах сетевой задачи размещения с ограничениями на пропускные способности коммуникаций
AU - Gimadi, Edward Khairutdinovich
AU - Tsidulko, Oxana Yurievna
N1 - Гимади Э.Х., Цидулко О.Ю. О некоторых эффективно разрешимых классах сетевой задачи размещения с ограничениями на пропускные способности коммуникаций // Тр. Ин-та математики и механики УрО РАН. - 2020. - Т.26. - № 2. - С. 108-124
PY - 2020/5/25
Y1 - 2020/5/25
N2 - В работе исследуется задача размещения в сетях с ограниченными пропускными способностями коммуникаций, в которой требуется разместить предприятия в вершинах заданной сети так, чтобы с минимальными затратами единовременно удовлетворить спросы всех клиентов, находящихся в вершинах сети. Рассматриваются постановки задачи с делимыми спросами, где спрос клиента может быть удовлетворен несколькими предприятиями совместно, и неделимыми спросами, тогда спрос клиента должен быть целиком удовлетворен одним предприятием. В работе показано, что задача с неделимыми спросами NP-трудна, даже если заданная сеть является простым путем, и NP-трудна в сильном смысле, если сеть - дерево. Задача с делимыми спросами слабо NP-трудна на деревьях. Для этой задачи в работе предложен псевдополиномиальный алгоритм решения на графах с древесной шириной, ограниченной константой, а также представлен линейный алгоритм для случая, когда граф сети является простым путем.
AB - В работе исследуется задача размещения в сетях с ограниченными пропускными способностями коммуникаций, в которой требуется разместить предприятия в вершинах заданной сети так, чтобы с минимальными затратами единовременно удовлетворить спросы всех клиентов, находящихся в вершинах сети. Рассматриваются постановки задачи с делимыми спросами, где спрос клиента может быть удовлетворен несколькими предприятиями совместно, и неделимыми спросами, тогда спрос клиента должен быть целиком удовлетворен одним предприятием. В работе показано, что задача с неделимыми спросами NP-трудна, даже если заданная сеть является простым путем, и NP-трудна в сильном смысле, если сеть - дерево. Задача с делимыми спросами слабо NP-трудна на деревьях. Для этой задачи в работе предложен псевдополиномиальный алгоритм решения на графах с древесной шириной, ограниченной константой, а также представлен линейный алгоритм для случая, когда граф сети является простым путем.
KW - Capacities
KW - Facility location problem
KW - Multiple-allocation
KW - NP-hard problem
KW - Polynomial-time algorithm
KW - Pseudopolynomial algorithm
KW - Single-allocation
KW - Treewidth
KW - tree-width
KW - UNSPLITTABLE FLOW
KW - pseudopolynomial algorithm
KW - PATHS
KW - ALGORITHMS
KW - facility location problem
KW - multiple-allocation
KW - TREES
KW - capacities
KW - single-allocation
KW - polynomial-time algorithm
UR - http://www.scopus.com/inward/record.url?scp=85090526044&partnerID=8YFLogxK
UR - https://www.elibrary.ru/item.asp?id=42950652
U2 - 10.21538/0134-4889-2020-26-2-108-124
DO - 10.21538/0134-4889-2020-26-2-108-124
M3 - статья
AN - SCOPUS:85090526044
VL - 26
SP - 108
EP - 124
JO - Trudy Instituta Matematiki i Mekhaniki UrO RAN
JF - Trudy Instituta Matematiki i Mekhaniki UrO RAN
SN - 0134-4889
IS - 2
ER -
ID: 25310375