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

}