Computational bounds for local search in combinatorial optimization

Yu. A. Kochetov

Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 48 (2008) no. 5, pp. 788-807

Résumé

The results related to finding local optima in combinatorial optimization are overviewed. The class of polynomial-time local search problems (class PLS) is considered. By analogy with Cook's theorem, the existence of most complicated problems in this class is established. The number of steps in local descent algorithms is estimated in the worst and average cases. The local search determination of exact and approximate solutions with guaranteed error bounds is discussed.

Bibliographie

[1] Arkhipova T. T., Sergienko I. V., “O formalizatsii i reshenii nekotorykh zadach organizatsii vychislitelnogo protsessa v sistemakh obrabotki dannykh”, Kibernetika, 1973, no. 5

[2] Arkhipova T. T., Sergienko I. V., “Metod vozmozhnykh napravlenii i metod vektora spada v tselochislennom programmirovanii”, Kibernetika, 1975, no. 5

[3] Volkonskii V. A., Levina L. V., Pomanskii A. B. i dr., “Ob odnom iterativnom metode resheniya zadach tselochislennogo programmirovaniya”, Dokl. AN SSSR, 169:6 (1966)

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

[5] Emelinev V. A., Kovalev M. M., Kononenko A. M., “Dva priblizhennykh metoda resheniya zadach tselochislennogo lineinogo programmirovaniya s bulevymi peremennymi”, Avtomatizirovannye sistemy upravleniya, Vyp. 5, TsNIITU, Minsk, 1971

[6] Zhuravlev Yu. I., “Lokalnye algoritmy vychisleniya informatsii”, Kibernetika, 1965, no. 1, 12–19 | MR

[7] Kovalev M. M., Piryanovich V. A., “Sluchainyi poisk lokalno-optimalnykh planov zadach diskretnoi optimizatsii”, Vopr. sovershenstvovaniya planirovaniya i upravleniya narodnym khozyaistvom, NIIEMP, Minsk, 1975

[8] Korbut A. A., Sigal I. Kh., Finkelshtein Yu. Yu., “Gibridnye metody v diskretnom programmirovanii”, Izv. AN SSSR. Tekhn. kibernetika, 1988, no. 1, 65–77

[9] Kochetov Yu. A., “Veroyatnostnye metody lokalnogo poiska dlya zadach diskretnoi optimizatsii”, Diskretnaya matem. i ee prilozh., MGU, M., 2001, 87–117

[10] Kochetov Yu. A., Paschenko M. G., Plyasunov A. B., “O slozhnosti lokalnogo poiska v zadache $p$-mediane”, Diskretnyi analiz i issl. operatsii. Ser. 2, 12:2 (2005), 44–71 | MR

[11] Lbov G. S., “Vybor effektivnoi sistemy zavisimykh priznakov”, Vychisl. sistemy, 19, 1965, 21–34

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

[13] Rastrigin L. A., “Sluchainyi poisk – spetsifika, etapy istorii i predrassudki”, Vopr. kibernetiki, 33, 1978, 3–16

[14] Sergienko I. V., “Primenenie metoda vektora spada dlya resheniya zadach tselochislennogo programmirovaniya”, Upravlyayuschie sistemy i mashiny, 1975, no. 3

[15] Sergienko I. V., Kaspshitskaya M. F., Modeli i metody resheniya na EVM kombinatornykh zadach optimizatsii, Nauk. dumka, Kiev, 1981 | MR

[16] Sigal I. Kh., “Posledovatelnost primeneniya algoritmov priblizhennogo resheniya v kombinirovannom algoritme resheniya zadachi kommivoyazhera”, Zh. vychisl. matem. i matem. fiz., 29:11 (1989), 1714–1721 | MR | Zbl

[17] Trubin V. A., “O metode resheniya zadach tselochislennogo lineinogo programmirovaniya spetsialnogo vida”, Dokl. AN SSSR, 189:5 (1969) | MR | Zbl

[18] Finkelshtein Yu. Yu., Priblizhennye metody i prikladnye zadachi diskretnogo programmirovaniya, Nauka, M., 1976

[19] Finkelshtein Yu. Yu., “Ob odnom klasse zadach diskretnogo programmirovaniya”, Ekonomika i matem. metody, 4:4 (1968), 652–655

[20] Finkelshtein Yu. Yu., “O reshenii zadach diskretnogo programmirovaniya spetsialnogo vida”, Ekonomika i matem. metody, 1:2 (1965), 262–270

[21] Ford L., Falkerson D., Potoki v setyakh, Mir, M., 1966 | Zbl

[22] Cherenin V. P., Khachaturov V. R., “Reshenie metodom posledovatelnykh raschetov odnogo klassa zadach o razmeschenii proizvodstva”, Ekonomiko-matem. metody, Vyp. 2, Nauka, M., 1965, 279–290

[23] Aarts E. H. L., Korst J. H. M., Laarhoven van P. J. M., “Simulated annealing”, Local Search in Combinatorial Optimizat., Wiley, Chichester, 1997, 91–120 | MR | Zbl

[24] Ahuja R. K., Ergun O., Orlin J. B., Purinen A. P., “A survey of very large-scale neighborhood search techniques”, Discrete Appl. Math., 123:1–3 (2002), 75–102 | DOI | MR | Zbl

[25] Alekseeva E., Kochetov Yu., Plyasunov A., “Complexity of local search for the $p$-median problem”, European J. Operat. Res., 191 (2008), 736–752 | DOI | MR | Zbl

[26] Angel E., Zissimopoulos V., “On the classification of NP-complete problems in terms of their correlation coefficient”, Discrete Appl. Math., 99 (2000), 261–277 | DOI | MR | Zbl

[27] Arora S., Raghavan P., Rao S., “Approximation schemes for Euclidean $k$-medians and related problems”, Proc. 30th Ann. ACM Symp. Theory of Comput., 1998, 106–113 | MR | Zbl

[28] Ausiello G., Crescenzi P., Gambosi G., Complexity and approximation: Combinatorial optimization problems and their approximability properties, Springer, Berlin, 1999 | MR | Zbl

[29] Bock F., “An algorithm for solving “travelling-salesman” and related network optimization problems”, Bull. Fourteenth Nat. Meeting of the Operat. Res. Soc. America, 1958, 897

[30] Burkard R. E., Deineko V. G., Woeginger G. J., “The traveling salesman problem and the PQ-tree”, Proc. IPCO V, Lect. Notes in Comput. Sci., 184, Springer, Berlin, 1996, 490–504 | MR

[31] E. K. Burke, G. Kendall (eds.), Search methodologies. Introductory tutorials in Optimization and Decision Support Techn., Springer, Berlin, 2005

[32] Croes G. A., “A method for solving traveling salesman problems”, Operat. Res., 6 (1958), 791–812 | DOI | MR

[33] Fabrikant A., Papadimitriou C., Talwar K., “The complexity of pure Nash equilibria”, Proc. 36th Ann. ACM Symp. Theory Comput., Chicago: IL USA, 2004, 604–612 | MR

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

[35] Fischer S. T., “A note on the complexity of local search problems”, Information Processing Letts., 53 (1995), 69–75 | DOI | MR | Zbl

[36] Fridman M. L., Johnson D. S., McGeoch L. A., Ostheimer G., “Data structures for traveling salesman”, J. Algorithms, 18 (1995), 432–479 | DOI | MR

[37] Grover L. K., “Local search and the local structure of NP-complete problems”, Operat. Res. Letts, 12:4 (1992), 235–244 | DOI | MR

[38] Guha S., Khuller S., “Greedy strikes back: improved facility location algorithms”, J. Algorithms, 31 (1999), 228–248 | DOI | MR | Zbl

[39] Gutin G., “Exponential neighborhood local search for the traveling salesman problem”, Comput. Operat. Res., 26 (1999), 313–320 | DOI | MR | Zbl

[40] Gutin G., Yeo A., “Small diameter neighborhood graphs for the traveling salesman problem: four moves from tour to tour”, Comput. Operat. Res., 26 (1999), 321–327 | DOI | MR | Zbl

[41] Johnson D. S., McGeoch L. A., “The traveling salesman problem: a case study”, Local Search in Combinatorial Optimizat., Wiley, Chichester, 215–310 | MR | Zbl

[42] Johnson D. S., “Local optimization and the traveling salesman problem”, Automata, Languages, and Programming, Lect. Notes in Comput. Sci., 443, Springer, Berlin, 1990, 446–61 | MR

[43] Johnson D. S., Papadimitriou C. H., Yannakakis M., “How easy is local search?”, J. Comput. and System Sci., 37 (1988), 79–100 | DOI | MR | Zbl

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

[45] Kochetov Yu., Ivanenko D., “Computationally difficult instances for the uncapacitated facility location problem”, Metaheuristics: Progress as Real Solvers, eds. T. Ibaraki et al., Springer, Berlin, 2005, 351–367

[46] Korte B., Vygen J., Combinatorial optimization. Theory and algorithms, 3th ed., Springer, Berlin, 2005 | Zbl

[47] Krentel M. W., “Structure in locally optimal solutions”, Proc. 3th Ann. Symp. Foundation Comput. Sci., 1989, 216–222

[48] Krentel M. W., “On finding and verifying locally optimal solutions”, SIAM J. Comput., 19 (1990), 742–751 | DOI | MR

[49] Lin S., Kernighan B. W., “An efficient heuristic algorithm for the traveling-salesman problem”, Operat. Res., 21 (1973), 498–516 | DOI | MR | Zbl

[50] Nicholson T. A. J., “A sequential method for discrete optimization problems and its application to the assignment, traveling salesman and tree scheduling problems”, J. Inst. Math. Appl., 13 (1965), 362–375

[51] Orlin J. B., Punnen A. P., Schulz A., “Approximate local search in combinatorial optimization”, SIAM J. Comput., 33 (2004), 1201–1214 | DOI | MR | Zbl

[52] Osman L. H., Laporte G., “Metaheuristics: a bibliography”, Ann. Operat. Res., 63 (1996), 513–628 | DOI | MR

[53] Papadimitriou C. H., “The complexity of the Lin-Kernighan heuristic for the traveling salesman problem”, SIAM J. Comput., 21 (1992), 450–463 | DOI | MR

[54] Punnen A. P., The traveling salesman problem: new polynomial approximation algorithms and domination analysis, Res. Rep. St. John, Univ. New Brunswick, 1996

[55] C. C. Ribeiro, P. Hansen (eds.), Meta-heuristics: advances and trends in local search paradigms for optimization, Kluwer. Acad. Publs, Boston, 1998

[56] 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

[57] Stadler P. F., “Corelation in landscapes of combinatorial optimization problems”, Europhys. Letts., 20 (1992), 479–482 | DOI

[58] Stadler P. F., Schnabl W., “The landscape of the traveling salesman problem”, Phys. Letts. A, 161 (1992), 337–344 | DOI | MR | Zbl

[59] Tovey C. A., “Low order polynomial bounds on the expected performance of local improvement algorithms”, Math. Program., 35 (1986), 193–224 | DOI | MR | Zbl

[60] Tovey C. A., “Local improvement on discrete structures”, Local Search in Combinatorial Optimizat., Wiley, Chichester, 1997, 57–90 | MR

[61] Verhoeven M. G. A., Swinkels P. C. J., Aarts E. H. L., Parallel local search and the traveling salesman problem, Working Paper, Philips Res. Labs., Eindhoven, 1995

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

[63] Weiner P., Savage S. L., Bagchi A., “Neighborhood search algorithms for guaranteeing optimal traveling salesman tours must be inefficient”, J. Comput. and System Sci., 12 (1976), 25–35 | MR | Zbl

[64] Yannakakis M., “Computational complexity”, Local Search in Combinatorial Optimizat., Wiley, Chichester, 1997, 19–55 | MR | Zbl

[65] Ausello G., Protasi M., “Local search reducibility and approximability of NP-optimization problems”, Information Proc. Letts., 54 (1995), 73–79 | DOI | MR