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

Edward Kh Gimadi; Anna A. Kurochkina

doi:10.1007/978-3-030-10934-9_9

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 proceeding › Conference contribution › Research › peer-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(m³n²) time, where m is the number of facilities and n is the number of clients. This improves the results O(m⁵n²) of Ageev in 2004 and O(m⁴n²) of Ageev, Gimadi, and Kurochkin in 2009.

Original language	English
Title of host publication	Optimization and Applications - 9th International Conference, OPTIMA 2018, Revised Selected Papers
Editors	Yury Kochetov, Michael Khachay, Yury Evtushenko, Vlasta Malkova, Mikhail Posypkin, Milojica Jacimovic
Publisher	Springer-Verlag GmbH and Co. KG
Pages	123-130
Number of pages	8
ISBN (Print)	9783030109332
DOIs	https://doi.org/10.1007/978-3-030-10934-9_9
Publication status	Published - 1 Jan 2019
Event	9th International Conference on Optimization and Applications, OPTIMA 2018 - Petrovac, Montenegro Duration: 1 Oct 2018 → 5 Oct 2018

Publication series

Name	Communications in Computer and Information Science
Volume	974
ISSN (Print)	1865-0929

Conference

Conference	9th International Conference on Optimization and Applications, OPTIMA 2018
Country	Montenegro
City	Petrovac
Period	01.10.2018 → 05.10.2018

Keywords

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

Access to Document

10.1007/978-3-030-10934-9_9

Link to publication in Scopus

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

Gimadi, Edward Kh ; Kurochkina, Anna A. / Time complexity of the ageev’s algorithm to solve the uniform hard capacities facility location problem. Optimization and Applications - 9th International Conference, OPTIMA 2018, Revised Selected Papers. editor / Yury Kochetov ; Michael Khachay ; Yury Evtushenko ; Vlasta Malkova ; Mikhail Posypkin ; Milojica Jacimovic. Springer-Verlag GmbH and Co. KG, 2019. pp. 123-130 (Communications in Computer and Information Science).

@inproceedings{0b824f8567634655b147abecb2ce1fc6,

title = "Time complexity of the ageev{\textquoteright}s algorithm to solve the uniform hard capacities facility location problem",

abstract = "We show that the facility location problem with uniform hard capacities can be solved by the Ageev{\textquoteright}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.",

keywords = "Capacitated, Dynamic programming technique, Exact algorithm, Facility location problem, Network, Path graph, Polynomial, Time complexity, Uniform",

author = "Gimadi, {Edward Kh} and Kurochkina, {Anna A.}",

year = "2019",

month = jan,

day = "1",

doi = "10.1007/978-3-030-10934-9_9",

language = "English",

isbn = "9783030109332",

series = "Communications in Computer and Information Science",

publisher = "Springer-Verlag GmbH and Co. KG",

pages = "123--130",

editor = "Yury Kochetov and Michael Khachay and Yury Evtushenko and Vlasta Malkova and Mikhail Posypkin and Milojica Jacimovic",

booktitle = "Optimization and Applications - 9th International Conference, OPTIMA 2018, Revised Selected Papers",

address = "Germany",

note = "9th International Conference on Optimization and Applications, OPTIMA 2018 ; Conference date: 01-10-2018 Through 05-10-2018",

}

Gimadi, EK & Kurochkina, AA 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. Communications in Computer and Information Science, vol. 974, Springer-Verlag GmbH and Co. KG, pp. 123-130, 9th International Conference on Optimization and Applications, OPTIMA 2018, Petrovac, Montenegro, 01.10.2018. https://doi.org/10.1007/978-3-030-10934-9_9

Time complexity of the ageev’s algorithm to solve the uniform hard capacities facility location problem. / Gimadi, Edward Kh; Kurochkina, Anna A.

Optimization and Applications - 9th International Conference, OPTIMA 2018, Revised Selected Papers. ed. / Yury Kochetov; Michael Khachay; Yury Evtushenko; Vlasta Malkova; Mikhail Posypkin; Milojica Jacimovic. Springer-Verlag GmbH and Co. KG, 2019. p. 123-130 (Communications in Computer and Information Science; Vol. 974).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review

TY - GEN

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

AU - Gimadi, Edward Kh

AU - Kurochkina, Anna A.

PY - 2019/1/1

Y1 - 2019/1/1

N2 - 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.

AB - 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.

KW - Capacitated

KW - Dynamic programming technique

KW - Exact algorithm

KW - Facility location problem

KW - Network

KW - Path graph

KW - Polynomial

KW - Time complexity

KW - Uniform

UR - http://www.scopus.com/inward/record.url?scp=85061215712&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-10934-9_9

DO - 10.1007/978-3-030-10934-9_9

M3 - Conference contribution

AN - SCOPUS:85061215712

SN - 9783030109332

T3 - Communications in Computer and Information Science

SP - 123

EP - 130

BT - Optimization and Applications - 9th International Conference, OPTIMA 2018, Revised Selected Papers

A2 - Kochetov, Yury

A2 - Khachay, Michael

A2 - Evtushenko, Yury

A2 - Malkova, Vlasta

A2 - Posypkin, Mikhail

A2 - Jacimovic, Milojica

PB - Springer-Verlag GmbH and Co. KG

T2 - 9th International Conference on Optimization and Applications, OPTIMA 2018

Y2 - 1 October 2018 through 5 October 2018

ER -

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