An exact polynomial algorithm for the outerplanar facility location problem with improved time complexity

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

Abstract

The Unbounded Facility Location Problem on outerplanar graphs is considered. The algorithm with time complexity O(nm3) was known for solving this problem, where n is the number of vertices, m is the number of possible plant locations. Using some properties of maximal outerplanar graphs (binary 2-trees) and the existence of an optimal solution with a family of centrally-connected service areas, the recurrence relations are obtained allowing to design an algorithm which can solve the problem in O(nm2.5) time.

Original languageEnglish
Title of host publicationAnalysis of Images, Social Networks and Texts - 6th International Conference, AIST 2017, Revised Selected Papers
EditorsWMP VanDerAalst, DI Ignatov, M Khachay, SO Kuznetsov, Lempitsky, IA Lomazova, N Loukachevitch, A Napoli, A Panchenko, PM Pardalos, AV Savchenko, S Wasserman
PublisherSpringer-Verlag GmbH and Co. KG
Pages295-303
Number of pages9
ISBN (Print)9783319730127
DOIs
Publication statusPublished - 1 Jan 2018
Event6th International Conference on Analysis of Images, Social Networks and Texts, AIST 2017 - Moscow, Russian Federation
Duration: 27 Jul 201729 Jul 2017

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10716 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference6th International Conference on Analysis of Images, Social Networks and Texts, AIST 2017
CountryRussian Federation
CityMoscow
Period27.07.201729.07.2017

Keywords

  • Dynamic programming
  • Exact algoritm
  • Outerplanar graph
  • Time complexity
  • Time complexity Dynamic programming
  • TREES

Fingerprint Dive into the research topics of 'An exact polynomial algorithm for the outerplanar facility location problem with improved time complexity'. Together they form a unique fingerprint.

  • Cite this

    Gimadi, E. (2018). An exact polynomial algorithm for the outerplanar facility location problem with improved time complexity. In WMP. VanDerAalst, DI. Ignatov, M. Khachay, SO. Kuznetsov, Lempitsky, IA. Lomazova, N. Loukachevitch, A. Napoli, A. Panchenko, PM. Pardalos, AV. Savchenko, & S. Wasserman (Eds.), Analysis of Images, Social Networks and Texts - 6th International Conference, AIST 2017, Revised Selected Papers (pp. 295-303). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10716 LNCS). Springer-Verlag GmbH and Co. KG. https://doi.org/10.1007/978-3-319-73013-4_27