### 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 language | English |
---|---|

Title of host publication | 2019 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019 |

Publisher | Institute of Electrical and Electronics Engineers Inc. |

Pages | 53-57 |

Number of pages | 5 |

ISBN (Electronic) | 9781728129860 |

DOIs | |

Publication status | Published - Aug 2019 |

Event | 15th International Asian School-Seminar on Optimization Problems of Complex Systems (OPCS) - Novosibirsk Duration: 26 Aug 2019 → 30 Aug 2019 |

### Publication series

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

### Conference

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

City | Novosibirsk |

Period | 26.08.2019 → 30.08.2019 |

### Keywords

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

## Cite this

*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