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

Edward Gimadi; Alexandr Shtepa; Oxana Tsidulko

doi:10.1109/OPCS.2019.8880248

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	https://doi.org/10.1109/OPCS.2019.8880248
Состояние	Опубликовано - авг 2019
Событие	15th International Asian School-Seminar on Optimization Problems of Complex Systems (OPCS) - Novosibirsk Продолжительность: 26 авг 2019 → 30 авг 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.2019 → 30.08.2019

Доступ к документу

10.1109/OPCS.2019.8880248

Link to publication in Scopus

Цитировать

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

Gimadi, Edward ; Shtepa, Alexandr ; Tsidulko, Oxana. / 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. Institute of Electrical and Electronics Engineers Inc., 2019. стр. 53-57 (2019 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019).

@inproceedings{21fc656434ec4461842ac6b6bf9a6dab,

title = "Improved Exact Algorithm for the Capacitated Facility Location Problem on a Line Graph",

abstract = "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",

keywords = "Capaciteted Facility Location Problem, line graph, pseudopolynomial-time algorithm, NP-hard problem, totally monotone matrix",

author = "Edward Gimadi and Alexandr Shtepa and Oxana Tsidulko",

year = "2019",

month = aug,

doi = "10.1109/OPCS.2019.8880248",

language = "English",

series = "2019 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "53--57",

booktitle = "2019 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019",

address = "United States",

note = "15th International Asian School-Seminar on Optimization Problems of Complex Systems (OPCS) ; Conference date: 26-08-2019 Through 30-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., 8880248, 2019 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019, Institute of Electrical and Electronics Engineers Inc., стр. 53-57, 15th International Asian School-Seminar on Optimization Problems of Complex Systems (OPCS), Novosibirsk, 26.08.2019. https://doi.org/10.1109/OPCS.2019.8880248

Improved Exact Algorithm for the Capacitated Facility Location Problem on a Line Graph. / Gimadi, Edward; Shtepa, Alexandr; Tsidulko, Oxana.

2019 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019. Institute of Electrical and Electronics Engineers Inc., 2019. стр. 53-57 8880248 (2019 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019).

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

TY - GEN

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

AU - Gimadi, Edward

AU - Shtepa, Alexandr

AU - Tsidulko, Oxana

PY - 2019/8

Y1 - 2019/8

N2 - 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

AB - 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

KW - Capaciteted Facility Location Problem

KW - line graph

KW - pseudopolynomial-time algorithm

KW - NP-hard problem

KW - totally monotone matrix

UR - http://www.scopus.com/inward/record.url?scp=85077985462&partnerID=8YFLogxK

U2 - 10.1109/OPCS.2019.8880248

DO - 10.1109/OPCS.2019.8880248

M3 - Conference contribution

T3 - 2019 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019

SP - 53

EP - 57

BT - 2019 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 15th International Asian School-Seminar on Optimization Problems of Complex Systems (OPCS)

Y2 - 26 August 2019 through 30 August 2019

ER -

Gimadi E, Shtepa A, Tsidulko O. 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. Institute of Electrical and Electronics Engineers Inc. 2019. стр. 53-57. 8880248. (2019 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019). https://doi.org/10.1109/OPCS.2019.8880248