An Effective Algorithm for the Three-Stage Facility Location Problem on a Tree-Like Network

Edward Kh Gimadi, Aleksandr S. Shevyakov

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

Abstract

In this article we consider a three-level facility location problem on a tree-like network under the restriction that the transportation costs for a unit of production from one node to another is equal to the sum of the edges in the path connecting these nodes. As a result we construct an exact algorithm for this problem and prove his complexity equeled O(nm6), where n is the number of the production demand points and, m is an upper bound on the number of possible facility location sites of each level.

Original languageEnglish
Title of host publicationRecent Trends in Analysis of Images, Social Networks and Texts - 9th International Conference, AIST 2020, Revised Supplementary Proceedings
EditorsWil M. van der Aalst, Vladimir Batagelj, Alexey Buzmakov, Dmitry I. Ignatov, Anna Kalenkova, Michael Khachay, Olessia Koltsova, Andrey Kutuzov, Sergei O. Kuznetsov, Irina A. Lomazova, Natalia Loukachevitch, Ilya Makarov, Amedeo Napoli, Alexander Panchenko, Panos M. Pardalos, Marcello Pelillo, Andrey V. Savchenko, Elena Tutubalina
PublisherSpringer Science and Business Media Deutschland GmbH
Pages267-274
Number of pages8
ISBN (Print)9783030712136
DOIs
Publication statusPublished - 2021
Event9th International Conference on Analysis of Images, Social Networks, and Texts, AIST 2020 - Virtual, Online
Duration: 15 Oct 202016 Oct 2020

Publication series

NameCommunications in Computer and Information Science
Volume1357 CCIS
ISSN (Print)1865-0929
ISSN (Electronic)1865-0937

Conference

Conference9th International Conference on Analysis of Images, Social Networks, and Texts, AIST 2020
CityVirtual, Online
Period15.10.202016.10.2020

Keywords

  • Polynomial-time algorithm
  • Three-level facility location problem
  • Tree-like network

OECD FOS+WOS

  • 1.02 COMPUTER AND INFORMATION SCIENCES
  • 1.01 MATHEMATICS

Fingerprint

Dive into the research topics of 'An Effective Algorithm for the Three-Stage Facility Location Problem on a Tree-Like Network'. Together they form a unique fingerprint.

Cite this