Improved Exact Algorithm for the Capacitated Facility Location Problem on a Line Graph

Edward Gimadi, Alexandr Shtepa, Oxana Tsidulko

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

Аннотация

In the Capacitated Facility Location Problem (CFLP) the goal is to optimally place facilities at the vertices of a transportation network graph in order to minimize the total facility opening and transportation costs while considering additional restrictions on the facility capacities. The general problem is NP-hard. In this paper we study a special case of the CFLP, where the input transportation network graph is a line graph. We show how to improve the running-time of the best known pseudopolynomial-time algorithm for the CFLP on a line graph from [Mirchandani et al., 1996] by one order

Язык оригиналаанглийский
Название основной публикации2019 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019
ИздательInstitute of Electrical and Electronics Engineers Inc.
Страницы53-57
Число страниц5
ISBN (электронное издание)9781728129860
DOI
СостояниеОпубликовано - авг 2019
Событие15th International Asian School-Seminar on Optimization Problems of Complex Systems (OPCS) - Novosibirsk
Продолжительность: 26 авг 201930 авг 2019

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

Название2019 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019

Конференция

Конференция15th International Asian School-Seminar on Optimization Problems of Complex Systems (OPCS)
ГородNovosibirsk
Период26.08.201930.08.2019

Цитировать

Gimadi, E., Shtepa, A., & Tsidulko, O. (2019). Improved Exact Algorithm for the Capacitated Facility Location Problem on a Line Graph. В 2019 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019 (стр. 53-57). [8880248] (2019 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/OPCS.2019.8880248