Geodesic
On the complexity of local search in the $p$-median problem
Diskretnyj analiz i issledovanie operacij, Tome 12 (2005) no. 2, pp. 44-71.

Voir la notice de l'article provenant de la source Math-Net.Ru

@article{DA_2005_12_2_a2,
     author = {Yu. A. Kochetov and M. G. Pashchenko and A. V. Plyasunov},
     title = {On the complexity of local search in the $p$-median problem},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {44--71},
     publisher = {mathdoc},
     volume = {12},
     number = {2},
     year = {2005},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2005_12_2_a2/}
}
TY  - JOUR
AU  - Yu. A. Kochetov
AU  - M. G. Pashchenko
AU  - A. V. Plyasunov
TI  - On the complexity of local search in the $p$-median problem
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2005
SP  - 44
EP  - 71
VL  - 12
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2005_12_2_a2/
LA  - ru
ID  - DA_2005_12_2_a2
ER  - 
%0 Journal Article
%A Yu. A. Kochetov
%A M. G. Pashchenko
%A A. V. Plyasunov
%T On the complexity of local search in the $p$-median problem
%J Diskretnyj analiz i issledovanie operacij
%D 2005
%P 44-71
%V 12
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2005_12_2_a2/
%G ru
%F DA_2005_12_2_a2
Yu. A. Kochetov; M. G. Pashchenko; A. V. Plyasunov. On the complexity of local search in the $p$-median problem. Diskretnyj analiz i issledovanie operacij, Tome 12 (2005) no. 2, pp. 44-71. http://geodesic.mathdoc.fr/item/DA_2005_12_2_a2/

[1] Geri M., Dzhonson D., Vychislitelnye mashiny i trudnoreshaemye zadachi, Mir, M., 1982 | MR

[2] Papadimitriu Kh., Staiglits K., Kombinatornaya optimizatsiya. Algoritmy i slozhnost, Mir, M., 1985 | MR

[3] Rodzhers Kh., Teoriya rekursivnykh funktsii i effektivnaya vychislimost, Mir, M., 1972 | MR

[4] Skhreiver A., Teoriya lineinogo i tselochislennogo programmirovaniya, Mir, M., 1991

[5] Atallah M., Algorithms and theory of computation handbook, CRC Press, Boca Raton, FL, 1999 | MR

[6] Ausiello G., Crescenzi P., Gambosi G., Kann V., Marchetti-Spaccamela A., Protasi M., Complexity and approximation: combinatorial optimization problems and their approximability properties, Springer, Berlin, 1999 | MR | Zbl

[7] Brucker P., Hurink J., Werner F., “Improving local search heuristics for some scheduling problems, I”, Discrete Appl. Math., 65:1–3 (1996), 97–122 | DOI | MR | Zbl

[8] Brucker P., Hurink J., Werner F., “Improving local search heuristics for some scheduling problems, II”, Discrete Appl. Math., 72:1–2 (1997), 47–69 | DOI | MR | Zbl

[9] Fiduccia C. M., Mattheyses R. M., “A linear-time heuristic for improving network partitions”, Proc. of the 19th Design Automation Conference, IEEE Comput. Soc. Press, Los Alamitos, CA, 1982, 175–181

[10] Fisher M. L., “Worst-case analysis of heuristic algorithms”, Manag. Sci., 26:1 (1980), 1–18 | DOI | MR

[11] Hansen P., Mladenović N., “Variable neighborhood search for the $p$-median”, Location Science, 5:4 (1997), 207–226 | DOI | MR | Zbl

[12] Hromkovič J., Algorithmics for hard problems, Springer, Berlin, 2004

[13] Johnson D. C., Papadimitriou C. H., Yannakakis M., “How easy is local search?”, J. Comput. and System Sciences, 37:1 (1988), 56–87 | MR

[14] Kernighan B. W., Lin S., “An effective heuristic procedure for partitioning graphs”, Bell System Techn. J., 49 (1970), 291–307 | Zbl

[15] Kochetov Yu., Alekseeva E., Levanova T., Loresh M., “Large neighborhood local search for the $p$-median problem”, Yugoslav Journal of Oper. Res., 15 (2005), 53–63 | DOI

[16] Mautor T., “Intensification neighborhoods for local search methods”, Essays and surveys in metaheuristics, Kluwer Academic Publishers, Boston, 2002, 493–508 | MR | Zbl

[17] Papadimitriou C. H., Addison-Wesley Publ. Company, Reading, MA, 1994 | MR

[18] Schäffer A. A., Yannakakis M., “Simple local search problems that are hard to solve”, SIAM J. Comput., 20:1 (1991), 56–87 | DOI | MR | Zbl

[19] Tovey C., “Local improvement on discrete structures”, Local search in combinatorial optimization, Wiley, Chichester, 1997, 57–89 | MR | Zbl

[20] Vredeveld T., Lenstra J. K., “On local search for the generalized graph coloring problem”, Oper. Res. Lett., 31:4 (2003), 28–34 | DOI | MR | Zbl

[21] Yannakakis M., “Computational complexity”, Local search in combinatorial optimization, Wiley, Chichester, 1997, 19–55 | MR | Zbl