How Fast Can the Uniform Capacitated Facility Location Problem Be Solved on Path Graphs

Alexander Ageev, Edward Gimadi, Alexandr Shtepa

Результат исследования: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференциинаучнаярецензирование

Аннотация

The Capacitated Facility Location Problem (CFLP) aims to open a subset of facilities, each of which has an opening cost and a capacity constraint, to serve all the given client demands such that the total transportation and facility opening costs are minimized. We consider the network CFLP in which the clients and the facilities are located at the vertices of a given edge-weighted transportation network graph. The network CFLP is NP-hard even when the network is a simple path. However, the Uniform CFLP (UCFLP) where the capacities of all facilities are identical is known to be polynomial-time solvable on path graphs. In this paper we revisit the dynamic programming algorithm by Ageev, Gimadi and Kurochkin [Diskret. Analys. Issl. Oper., 2009] for the UCFLP on path graphs and show how its time complexity can be improved to O(m2n2), where m is the number of possible facility locations, n is the number of clients, which is the best possible time complexity within the framework of the considered algorithm. Also we carried out the comparison of the proposed strictly polynomial algorithm with the best pseudo-polynomial algorithms.

Язык оригиналаанглийский
Название основной публикацииAnalysis of Images, Social Networks and Texts - 10th International Conference, AIST 2021, Revised Selected Papers
РедакторыEvgeny Burnaev, Sergei Ivanov, Alexander Panchenko, Dmitry I. Ignatov, Sergei O. Kuznetsov, Michael Khachay, Olessia Koltsova, Andrei Kutuzov, Natalia Loukachevitch, Amedeo Napoli, Panos M. Pardalos, Jari Saramäki, Andrey V. Savchenko, Evgenii Tsymbalov, Elena Tutubalina
ИздательSpringer Science and Business Media Deutschland GmbH
Страницы303-314
Число страниц12
ISBN (печатное издание)9783031164996
DOI
СостояниеОпубликовано - 2022
Событие10th International Conference on Analysis of Images, Social Networks and Texts, AIST 2021 - Tbilisi, Грузия
Продолжительность: 16 дек. 202118 дек. 2021

Серия публикаций

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том13217 LNCS
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349

Конференция

Конференция10th International Conference on Analysis of Images, Social Networks and Texts, AIST 2021
Страна/TерриторияГрузия
ГородTbilisi
Период16.12.202118.12.2021

Предметные области OECD FOS+WOS

  • 1.02 КОМПЬЮТЕРНЫЕ И ИНФОРМАЦИОННЫЕ НАУКИ
  • 1.01 МАТЕМАТИКА

Fingerprint

Подробные сведения о темах исследования «How Fast Can the Uniform Capacitated Facility Location Problem Be Solved on Path Graphs». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать