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

Edward Gimadi, Alexandr Shtepa, Oxana Tsidulko

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

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

Original languageEnglish
Title of host publication2019 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages53-57
Number of pages5
ISBN (Electronic)9781728129860
DOIs
Publication statusPublished - Aug 2019
Event15th International Asian School-Seminar on Optimization Problems of Complex Systems (OPCS) - Novosibirsk
Duration: 26 Aug 201930 Aug 2019

Publication series

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

Conference

Conference15th International Asian School-Seminar on Optimization Problems of Complex Systems (OPCS)
CityNovosibirsk
Period26.08.201930.08.2019

Keywords

  • Capaciteted Facility Location Problem
  • line graph
  • pseudopolynomial-time algorithm
  • NP-hard problem
  • totally monotone matrix

Cite this

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