Polynomial algorithm for the path facility location problem with uniform capacities

A. A. Ageev ; E. Kh. Gimadi ; A. A. Kurochkin

Diskretnyj analiz i issledovanie operacij, Tome 16 (2009) no. 5, pp. 3-18.

Résumé

The Facility Location Problem with uniform capacities on path graphs is considered. Earlier it was shown by Ageev that this problem can be solved in $O(m^3n^3+m^5n^2)$ time, where $m$ is the number of facilities and $n$ is the number of clients. In the paper the modified algorithm is presented that has reduced infinitesimal order for the time complexity $O(m^4n^2)$. Ill. 9, bibl. 24.

Détail

Keywords: facility location, uniform capacities, path graphs
Mots-clés : polynomial-time algorithm.

Bibliographie

[1] Ageev A. A., “Polinomialnyi algoritm resheniya zadachi razmescheniya na posledovatelno-parallelnoi seti”, Upravlyaemye sistemy, Sb. nauch. tr., Vyp. 30, In-t matematiki SO RAN, Novosibirsk, 1990, 3–16 | MR

[2] Beresnev V. L., Gimadi E. Kh., Dementev V. T., Ekstremalnye zadachi standartizatsii, Nauka, Novosibirsk, 1978, 333 pp. | MR

[3] Voznyuk I. P., Gimadi E. Kh., Filatov M. Yu., “Asimptoticheski tochnyi algoritm dlya resheniya zadachi razmescheniya s ogranichennymi ob'emami proizvodstva”, Diskret. analiz i issled. operatsii. Ser. 2, 8:2 (2001), 3–16 | MR | Zbl

[4] Gimadi E. Kh., “Effektivnyi algoritm resheniya zadachi razmescheniya s oblastyami obsluzhivaniya, svyaznymi otnositelno atsiklicheskoi seti”, Upravlyaemye sistemy, Sb. nauch. tr., Vyp. 23, In-t matematiki SO AN SSSR, Novosibirsk, 1983, 12–23 | MR

[5] Gimadi E. Kh., “Zadacha razmescheniya na seti s tsentralno-svyaznymi oblastyami obsluzhivaniya”, Upravlyaemye sistemy, Sb. nauch. tr., Vyp. 25, In-t matematiki SO AN SSSR, Novosibirsk, 1984, 38–47 | MR

[6] Gimadi E. Kh., “Zadacha standartizatsii s dannymi proizvolnogo znaka i svyaznymi, kvazivypuklymi i pochti kvazivypuklymi matritsami”, Upravlyaemye sistemy, Sb. nauch. tr., Vyp. 27, In-t matematiki SO AN SSSR, Novosibirsk, 1987, 3–11 | MR

[7] Gimadi E. Kh., “Effektivnye algoritmy dlya resheniya mnogoetapnoi zadachi razmescheniya na tsepi”, Diskret. analiz i issled. operatsii, 2:4 (1995), 13–31 | MR | Zbl

[8] Geri M. R., Dzhonson D. S., Vychislitelnye mashiny i trudnoreshaemye zadachi, Mir, M., 1982, 416 pp. | MR

[9] Ageev A. A., “A polynomial-time solvability for the network location problem”, Integer programming and combinatorial optimization, Proc. IPCO II Conf. Campus Printing, Carnegi Mellon University, Pittsburg, 1992, 237–245

[10] Ageev A. A., “A polynomial-time algorithm for the facility location problem with uniform hard capacities on path graph”, Proc. of the 2nd Intern. workshop “Discrete optimization methods in production and logistics”, DOM' 2004, Nasledie–Dialog Sibir Pbs, Omsk, 2004, 28–32

[11] Billionet A., Costa M.-C., “Solving the uncapacitated plant location problem on trees”, Discr. Appl. Math., 49:1–3 (1994), 51–59 | DOI | MR

[12] Chudak F. A., Williamson D., “Improved approximation algorithms for capacitated facility location problems”, Lect. Notes in Comp. Sci., 1610, 1999, 99–113 | MR | Zbl

[13] Cornuéjols G., Nemhauser G. L., Wolsey L. A., “The uncapacitated facility location problem”, Discrete location theory, Wiley, New York, 1990, 119–171 | MR

[14] Gimadi E. Kh., “Exact algorithms for some multi-level location problems on a chain and a tree”, Oper. Res. Proc. 1996, SOR96, Springer–Verl., Berlin–Heidelberg, 1997, 72–77 | MR | Zbl

[15] Hassin R., Tamir A., “Efficient algorithms for optimization on series-parallel graphs”, SIAM J. Algebraic Discrete Methods, 7:3 (1986), 379–386 | DOI | MR

[16] Korupolu M. R., Plaxton C. G., Rajaraman R., “Analysis of a local search heuristic”, Proc. of the 9th Ann. ACM-SIAM Symp. on discrete algorithms, SODA, San Francisco, CA, 1998, 1–10 | MR

[17] Mahdian M., Pál M., “Universal facility location”, Lect. Notes in Comp. Sci., 2832, 2003, 409–421 | MR

[18] Mirchandani P., Kohli R., Tamir A., “Capacitated location problems on a line”, Transportation Sci., 30:1 (1996), 75–80 | DOI | MR | Zbl

[19] Mirchandani P. B., Francis R. L., Discrete location theory, Wiley-Interscience series in discrete mathematics and optimization, Wiley, New York, 1990, 576 pp. | MR | Zbl

[20] Pál M., Tardos E., Wexler T., “Facility location with hard capacities”, Proc. of the 42nd Ann. Symp. on foundations of computer science, FOCS, Las Vegas, Nevada, USA, 2001, 320–328 | MR

[21] Shah D., “An unified limited column generation approach for facility location problem on trees”, Ann. Oper. Research, 87 (1999), 363–382 | DOI | MR

[22] Shah R., Farach-Colton V., “Undiscretized dynamic programming: faster algorithms for facility location and related problems on trees”, Proc. of the 13th Ann. ACM-SIAM Symp. on discrete algorithms, SODA, San Francisco, California, 2002, 108–115

[23] Tamir A., Lowe T., “The generalized $p$-forest problem on a tree network”, Networks, 22 (1992), 217–230 | DOI | MR | Zbl

[24] Zhang J., Chen B., Ye Y., “A multi-exchange local search algorithm for the capacitated facility location problem”, Mathematics on Operation Research, 30:2, May (2005), 389–403 | DOI | MR | Zbl