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