Standard

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

Harvard

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

APA

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

Vancouver

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). doi: 10.1007/978-3-030-10934-9_9

Author

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

BibTeX

@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",

}

RIS

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 -

ID: 18488916