|
|
Вторая конференция Математических центров России. Секция «Прикладная математика и математическое моделирование»
10 ноября 2022 г. 17:35–18:00, г. Москва, ИВМ РАН, аудитория 727
|
|
|
|
|
|
Facility location problems with capacity constraints on tree-like graphs
О. Ю. Цидулко |
Количество просмотров: |
Эта страница: | 30 | Материалы: | 1 |
|
Аннотация:
В классической сетвой задаче размещения (Facility Location Problem, FLP) требуется разместить предприятия в вершинах заданного графа сети так, чтобы с минимальн
ыми затратами на открытие предприятий и транспортировку продукта единовременно удовлетворить спросы всех клиентов, находящихся в вершинах сети. Естественным обо
бщением классической задачи являются задачи с дополнительными ограничениями на объемы производства предприятий (Capacitated FLP, CFLP), а также с ограничениями
на пропускные способности коммуникаций сети (Restricted FLP, RFLP). В докладе рассматриваются задачи RFLP и однородная CFLP на простейших типах графов таких ка
к пути, звезды, деревья, графы с ограниченной древовидной шириной. Приводятся недавние результаты, полученные совместно с соавторами, по уточнению сложностного
статуса и построению точных полиномиальных (и даже линейных), а также псевдополиномиальных алгоритмов решения для частных случаев рассматриваемых задач.
Дополнительные материалы:
ЦидулкоОЮ.pdf (573.6 Kb)
|
|