Standard

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. p. 53-57 8880248 (2019 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review

Harvard

Gimadi, E, Shtepa, A & Tsidulko, O 2019, Improved Exact Algorithm for the Capacitated Facility Location Problem on a Line Graph. in 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., pp. 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

APA

Gimadi, E., Shtepa, A., & Tsidulko, O. (2019). Improved Exact Algorithm for the Capacitated Facility Location Problem on a Line Graph. In 2019 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019 (pp. 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

Vancouver

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

Author

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. pp. 53-57 (2019 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019).

BibTeX

@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",

}

RIS

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 -

ID: 24159543