An effective local search for the maximum clique problem. (English) Zbl 1185.68283
Summary: We propose a variable depth search based algorithm, called \(k\)-opt local search \((KLS)\), for the maximum clique problem. \(KLS\) efficiently explores the \(k\)-opt neighborhood defined as the set of neighbors that can be obtained by a sequence of several add and drop moves that are adaptively changed in the feasible search space. Computational results on DIMACS benchmark graphs indicate that \(KLS\) is capable of finding considerably satisfactory cliques with reasonable running times in comparison with those of state-of-the-art metaheuristics.
MSC:
| 68P10 | Searching and sorting |
| 68R10 | Graph theory (including graph drawing) in computer science |
| 68W05 | Nonnumerical algorithms |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
Keywords:
graph algorithms; combinatorial optimization; variable depth search; neighborhood; maximum clique problemReferences:
| [1] | Abello, J.; Pardalos, P. M.; Resende, M. G.C., On maximum clique problems in very large graphs, (Abello, J.; Vitter, J., External Memory Algorithms and Visualization. External Memory Algorithms and Visualization, DIMACS Series on Discrete Mathematics and Theoretical Computer Science, vol. 50 (1999), Amer. Math. Soc.: Amer. Math. Soc. Providence, RI), 119-130 · Zbl 0947.68119 |
| [2] | Applegate, D.; Cook, W.; Rohe, A., Chained Lin-Kernighan for large traveling salesman problems, INFORMS J. Comput., 15, 1, 82-92 (2003) · Zbl 1238.90125 |
| [3] | S. Arora, C. Lund, R. Motwani, M. Sudan, M. Szegedy, Proof verification and the hardness of approximation problems, in: Proc. 33rd Annual Symp. on Foundations of Computer Science, 1992, pp. 14-23; S. Arora, C. Lund, R. Motwani, M. Sudan, M. Szegedy, Proof verification and the hardness of approximation problems, in: Proc. 33rd Annual Symp. on Foundations of Computer Science, 1992, pp. 14-23 · Zbl 0977.68539 |
| [4] | Battiti, R.; Protasi, M., Reactive local search for the maximum clique problem, Algorithmica, 29, 4, 610-637 (2001) · Zbl 0985.68016 |
| [5] | Bomze, I. M.; Budinich, M.; Pelillo, M.; Rossi, C., Annealed replication: a new heuristic for the maximum clique problem, Discrete Appl. Math., 121, 27-49 (2002) · Zbl 1019.90032 |
| [6] | Bomze, I. M.; Budinich, M.; Pardalos, P. M.; Pelillo, M., The maximum clique problem, (Du, D. Z.; Pardalos, P. M., Handbook of Combinatorial Optimization (suppl. vol. A) (1999), Kluwer: Kluwer Dordrecht), 1-74 · Zbl 1253.90188 |
| [7] | Burer, S.; Monteiro, R. D.C.; Zhang, Y., Maximum stable set formulations and heuristics based on continuous optimization, Math. Programming, 94, 137-166 (2002) · Zbl 1023.90071 |
| [8] | Cavique, L.; Rego, C.; Themido, I., A scatter search algorithm for the maximum clique problem, (Essays and Surveys in Metaheuristics (2001), Kluwer: Kluwer Dordrecht), 227-244 · Zbl 1006.90069 |
| [9] | Eiben, A. E.; Schoenauer, M., Evolutionary computing, Inform. Process. Lett., 82, 1, 1-6 (2002) · Zbl 1013.68163 |
| [10] | U. Feige, S. Goldwasser, L. Lovász, S. Safra, M. Szegedy, Approximating clique is almost NP-complete, in: Proc. 32nd Annual Symp. on Foundations of Computer Science, San Juan, Puerto Rico, 1991, pp. 2-12; U. Feige, S. Goldwasser, L. Lovász, S. Safra, M. Szegedy, Approximating clique is almost NP-complete, in: Proc. 32nd Annual Symp. on Foundations of Computer Science, San Juan, Puerto Rico, 1991, pp. 2-12 |
| [11] | Fenet, S.; Solnon, C., Searching for maximum cliques with ant colony optimization, (Applications of Evolutionary Computing. Applications of Evolutionary Computing, Lecture Notes in Comput. Sci., vol. 2611 (2003), Springer: Springer Berlin), 236-245 · Zbl 1033.68623 |
| [12] | Feo, T. A.; Resende, M. G.C.; Smith, S. H., A greedy randomized adaptive search procedure for maximum independent set, Oper. Res., 42, 860-878 (1994) · Zbl 0815.90121 |
| [13] | Funabiki, N.; Takefuji, Y.; Lee, K. C., A neural network model for finding a near-maximum clique, Parallel Distrib. Comput., 14, 3, 340-344 (1992) |
| [14] | Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), Freeman: Freeman New York · Zbl 0411.68039 |
| [15] | Glover, F.; Laguna, M., Tabu Search (1998), Kluwer: Kluwer Dordrecht · Zbl 0954.90069 |
| [16] | Håstad, J., Clique is hard to approximate within \(n^{1 - \epsilon}\), Acta Math., 182, 105-142 (1999) · Zbl 0989.68060 |
| [17] | (Johnson, D. S.; Trick, M. A., Cliques, Coloring, and Satisfiability, Second DIMACS Implementation Challenge. Cliques, Coloring, and Satisfiability, Second DIMACS Implementation Challenge, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 26 (1996), Amer. Math. Soc.: Amer. Math. Soc. Providence, RI) |
| [18] | D.S. Johnson, Local optimization and the traveling salesman problem, in: Proc. 17th Internat. Colloquium on Automata, Languages and Programming, 1990, pp. 446-461; D.S. Johnson, Local optimization and the traveling salesman problem, in: Proc. 17th Internat. Colloquium on Automata, Languages and Programming, 1990, pp. 446-461 · Zbl 0766.90079 |
| [19] | K. Katayama, M. Tani, H. Narihisa, Solving large binary quadratic programming problems by effective genetic local search algorithm, in: Proc. Genetic and Evolutionary Computation Conf., 2000, pp. 643-650; K. Katayama, M. Tani, H. Narihisa, Solving large binary quadratic programming problems by effective genetic local search algorithm, in: Proc. Genetic and Evolutionary Computation Conf., 2000, pp. 643-650 |
| [20] | K. Katayama, H. Narihisa, Iterated local search approach using genetic transformation to the traveling salesman problem, in: Proc. Genetic and Evolutionary Computation Conf., 1999, pp. 321-328; K. Katayama, H. Narihisa, Iterated local search approach using genetic transformation to the traveling salesman problem, in: Proc. Genetic and Evolutionary Computation Conf., 1999, pp. 321-328 |
| [21] | Kernighan, B. W.; Lin, S., An efficient heuristic procedure for partitioning graphs, Bell System Techn. J., 49, 291-307 (1970) · Zbl 0333.05001 |
| [22] | Lin, S.; Kernighan, B. W., An effective heuristic algorithm for the traveling salesman problem, Oper. Res., 21, 498-516 (1973) · Zbl 0256.90038 |
| [23] | Marchiori, E., Genetic, iterated and multistart local search for the maximum clique problem, (Applications of Evolutionary Computing. Applications of Evolutionary Computing, Lecture Notes in Comput. Sci., vol. 2279 (2002), Springer: Springer Berlin), 112-121 · Zbl 1044.68780 |
| [24] | Merz, P.; Katayama, K., Memetic algorithms for the unconstrained binary quadratic programming problem, Biosystems, 78, 1-3, 99-118 (2004) |
| [25] | Merz, P.; Freisleben, B., Greedy and local search heuristics for unconstrained binary quadratic programming, J. Heuristics, 8, 2, 197-213 (2002) · Zbl 1013.90100 |
| [26] | Merz, P.; Freisleben, B., Memetic algorithms for the traveling salesman problem, Complex Systems, 13, 4, 297-345 (2001) · Zbl 1167.90693 |
| [27] | Merz, P.; Freisleben, B., Fitness landscapes, memetic algorithms and greedy operators for graph bipartitioning, Evolutionary Comput., 8, 1, 61-91 (2000) |
| [28] | Östergård, P. R.J., A fast algorithm for the maximum clique problem, Discrete Appl. Math., 120, 195-205 (2002) |
| [29] | Prestwich, S., Combining the scalability of local search with the pruning techniques of systematic search, Ann. Oper. Res., 115, 51-72 (2002) · Zbl 1013.90104 |
| [30] | Tomita, E.; Seki, T., An efficient branch-and-bound algorithm for finding a maximum clique, (Proc. 4th Internat. Conf. on Discrete Mathematics and Theoretical Computer Science. Proc. 4th Internat. Conf. on Discrete Mathematics and Theoretical Computer Science, Lecture Notes in Comput. Sci., vol. 2731 (2003), Springer: Springer Berlin), 278-289 · Zbl 1038.68565 |
| [31] | Yagiura, M.; Yamaguchi, T.; Ibaraki, T., A variable depth search algorithm for the generalized assignment problem, (Voss, S.; Martello, S.; Osman, I. H.; Roucairol, C., Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization (1999), Kluwer: Kluwer Dordrecht), 459-471 · Zbl 0985.90079 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
