Facility location problems with capacity constraints on tree-like graphs

В классической сетвой задаче размещения (Facility Location Problem, FLP) требуется разместить предприятия в вершинах заданного графа сети так, чтобы с минимальн ыми затратами на открытие предприятий и транспортировку продукта единовременно удовлетворить спросы всех клиентов, находящихся в вершинах сети. Естественным обо бщением классической задачи являются задачи с дополнительными ограничениями на объемы производства предприятий (Capacitated FLP, CFLP), а также с ограничениями на пропускные способности коммуникаций сети (Restricted FLP, RFLP). В докладе рассматриваются задачи RFLP и однородная CFLP на простейших типах графов таких ка к пути, звезды, деревья, графы с ограниченной древовидной шириной. Приводятся недавние результаты, полученные совместно с соавторами, по уточнению сложностного статуса и построению точных полиномиальных (и даже линейных), а также псевдополиномиальных алгоритмов решения для частных случаев рассматриваемых задач.