Time complexity of the ageev’s algorithm to solve the uniform hard capacities facility location problem

Edward Kh Gimadi, Anna A. Kurochkina

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

1 Citation (Scopus)

Abstract

We show that the facility location problem with uniform hard capacities can be solved by the Ageev’s algorithm in O(m3n2) time, where m is the number of facilities and n is the number of clients. This improves the results O(m5n2) of Ageev in 2004 and O(m4n2) of Ageev, Gimadi, and Kurochkin in 2009.

Original languageEnglish
Title of host publicationOptimization and Applications - 9th International Conference, OPTIMA 2018, Revised Selected Papers
EditorsYury Kochetov, Michael Khachay, Yury Evtushenko, Vlasta Malkova, Mikhail Posypkin, Milojica Jacimovic
PublisherSpringer-Verlag GmbH and Co. KG
Pages123-130
Number of pages8
ISBN (Print)9783030109332
DOIs
Publication statusPublished - 1 Jan 2019
Event9th International Conference on Optimization and Applications, OPTIMA 2018 - Petrovac, Montenegro
Duration: 1 Oct 20185 Oct 2018

Publication series

NameCommunications in Computer and Information Science
Volume974
ISSN (Print)1865-0929

Conference

Conference9th International Conference on Optimization and Applications, OPTIMA 2018
CountryMontenegro
CityPetrovac
Period01.10.201805.10.2018

Keywords

  • Capacitated
  • Dynamic programming technique
  • Exact algorithm
  • Facility location problem
  • Network
  • Path graph
  • Polynomial
  • Time complexity
  • Uniform

Fingerprint Dive into the research topics of 'Time complexity of the ageev’s algorithm to solve the uniform hard capacities facility location problem'. Together they form a unique fingerprint.

  • Cite this

    Gimadi, E. K., & Kurochkina, A. A. (2019). Time complexity of the ageev’s algorithm to solve the uniform hard capacities facility location problem. In Y. Kochetov, M. Khachay, Y. Evtushenko, V. Malkova, M. Posypkin, & M. Jacimovic (Eds.), Optimization and Applications - 9th International Conference, OPTIMA 2018, Revised Selected Papers (pp. 123-130). (Communications in Computer and Information Science; Vol. 974). Springer-Verlag GmbH and Co. KG. https://doi.org/10.1007/978-3-030-10934-9_9