A New Effective Local Search Heuristic for the Maximum Clique Problem
An edge based local search algorithm, called ELS, is proposed for the maximum clique problem (MCP), a well-known combinatorial optimization problem. ELS is a two phased local search method effectively £nds the near optimal solutions for the MCP. A parameter ’support’ of vertices de£ned in the ELS greatly reduces the more number of random selections among vertices and also the number of iterations and running times. Computational results on BHOSLIB and DIMACS benchmark graphs indicate that ELS is capable of achieving state-of-the-art-performance for the maximum clique with reasonable average running times.
<p>[1] S. Lin, B. W. Kernighan, An effective heuristic algorithm for traveling
salesman problem, Oper. Res. 21 (1973) 498-516.
[2] B. W. Kernighan, S. Lin, An ef£cient heuristic procedure for partitioning
graphs, Bell System Techn. J. 49 (1970) 291-307.
[3] K. Katayama, H. Narihisa, Iterated local search approach using genetic
transformation to the traveling salesman problem, Proceedings of the
Genetic and Evolutionary Computation Conference, (1999) 321-328
[4] D. Applegate, W. Cook, A. Rohe, Chained Lin-Kernighan for large
traveling salesman problems, Informs Journal of Computing, 15(1) (2003)
82-92.
[5] P. Merz, B. Freisleben, Memetic algorithms for the traveling salesman
problem, Complex Systems, 13(4) (2001) 297-345.
[6] P. Merz, B. Freisleben, Fitness landscapes, memetic algorithms and
greedy operators for graph partitioning, Evolutionary Computing, 8(1)
(2000) 61-91.
[7] M. Yaguira, T. Yamaguchi, T. Ibaraki, A variable depth search algorithm
for the generalized assignment problem, in S. Voss, S. Martello, I. H.
Osman, C. Roucairol(Eds.), Meta-Heuristics: Advance and Trends in
Local Search Paradigms for Optimization, Kluwer, Dordrecht, (1999)
459-471.
[8] P. Merz, K. Katayama, Memetic algorithms for the unconstrained binary
quadratic programming problem, Biosystems, 78(1-3) (2004) 99-118.
[9] K. Katayama, A. Hamamoto, H. Nirihisa, An effective local search for
the maximum clique problem, Information Processing Letters, 95 (2005)
503-511.
[10] W. Pullan, Phased local search for the maximum clique problem, J.
Comb. Optim. 12 (2006) 303-323.
[11] D. S. Johnson, M. A. Trick (Eds.): Cliques, Coloring and sats£ability,
Second DIMACS Implementation Challenge, DIMACS Series in Discrete
Mathematics and Theoretical Computer Science, Vol. 26, American
Mathematical Society, Providence, RI, 1996.
[12] P. A. Pevzner, S.-H. Sze, Combinatorial approaches to £nding subtle
signals in DNA sequences, in proceedings of Eighth International Conference
on intelligent systems for Molecular Biology, AIAA Press, New
York, (2000) 269-278.
[13] Y. Ji, X. Xu, G. D. Stormo, A graph theoretical approach for predicting
common RNA secondary structure motifs including pseudoknots in
unaligned sequences. Bioinformatics 20(10) (2004) 1591-1602.
[14] M. R. Garey, D. S. Johnson: Computers and Intractability: A Guide to
the theory NP - completeness. San Francisco: Freeman (1979).
[15] J. Hastad: Clique is hard to approximate within n1- , Acta Mathematica,
182 (1999) 105-142.
[16] R. Boppana, M. Halldorsson, Approximating maximum independent sets
by excluding subgraphs. Bit 32 (1992) 180-196.
[17] X. Geng, J. Xu, J. Xiao and L. Pan: A simple simulated annealing
algorithm for the Maximum Clique problem”, 177 (2007) 5064-5071.
[18] E. Tomita, T. Kameda, An ef£cient branch-and-bound algorithm for
£nding a maximum clique with computational experiments, J. Glob.
Optim. 37 (2007) 95-111.
[19] P. R. J. Ostergard: A fast algorithm for the maximum clique problem,
Discrete Applied Mathematics, 120 (2002) 197-207.
[20] E. Balas, W. Niehaus, Optimized crossover-Based Genetic Algorithm
for the Maximum Cardinality and Maximum Weight Clique Problems,
Journal of Heuristics, 4 (1998) 107-122.
[21] S. Busygin, A new trust region technique for the maximum weight clique
problem, Discrete Applied Mathematics, 154 (2006) 2080-2096.
[22] G. -Marin, E. -Casermeiro, J. -Perez, Modelling competitive Hop£eld
networks for the maximum clique problem, Computers & Operations
Research, 30 (2003) 603-624.
[23] W. Pullan, H. H. Hoos, Dynamic local search for the maximum clique
problem, Journal of Arti£cial Intelligence Research, 25 (2006) 159-185.
[24] W. Pullan, Approximating the maximum vertex/edge weighted clique
using local search, J. Heuristics, 14 (2008) 117-134.
[25] P. J. Taillon, A new approach for solving the maximum clique problem,
LNCS, Springer-Verlag Berlin Heidelberg, 4041 (2006) 279-290.
[26] V. C. Barbosa, C. D. Campos, A novel evolutionary formulation of the
maximum independent set problem, J. Comb. Optim. 8 (2004) 419-437.
[27] B. Alidaee, G. Kochenberger, H. Wang, Simple and fast surrogate constraint
heuristics for the maximum independent set problem, J. Heuristics,
14 (2008) 571-585.
[28] T. S. Feo, M. G. C. Resende, S. H. Smith, A greedy randomized adaptive
search procedure for maximum independent set, Operations Research,
42(5) (1994) 860-978.
[29] S. Balaji, V. Swaminathan, K. Kannan: Approximating maximum
weighted independent set using vertex Support, International Journal of
Computational and Mathemtical Sciences1, 3(8) (2009) 406-411.
[30] S. Balaji, N. Revathi: An Ef£cient approach for the Optimization
version of Maximum Weighted Clique Problem, WSEAS Transactions
on Mathematics, 11(9) (2012) 773-783.</p>
<p>[1] S. Lin, B. W. Kernighan, An effective heuristic algorithm for traveling
salesman problem, Oper. Res. 21 (1973) 498-516.
[2] B. W. Kernighan, S. Lin, An ef£cient heuristic procedure for partitioning
graphs, Bell System Techn. J. 49 (1970) 291-307.
[3] K. Katayama, H. Narihisa, Iterated local search approach using genetic
transformation to the traveling salesman problem, Proceedings of the
Genetic and Evolutionary Computation Conference, (1999) 321-328
[4] D. Applegate, W. Cook, A. Rohe, Chained Lin-Kernighan for large
traveling salesman problems, Informs Journal of Computing, 15(1) (2003)
82-92.
[5] P. Merz, B. Freisleben, Memetic algorithms for the traveling salesman
problem, Complex Systems, 13(4) (2001) 297-345.
[6] P. Merz, B. Freisleben, Fitness landscapes, memetic algorithms and
greedy operators for graph partitioning, Evolutionary Computing, 8(1)
(2000) 61-91.
[7] M. Yaguira, T. Yamaguchi, T. Ibaraki, A variable depth search algorithm
for the generalized assignment problem, in S. Voss, S. Martello, I. H.
Osman, C. Roucairol(Eds.), Meta-Heuristics: Advance and Trends in
Local Search Paradigms for Optimization, Kluwer, Dordrecht, (1999)
459-471.
[8] P. Merz, K. Katayama, Memetic algorithms for the unconstrained binary
quadratic programming problem, Biosystems, 78(1-3) (2004) 99-118.
[9] K. Katayama, A. Hamamoto, H. Nirihisa, An effective local search for
the maximum clique problem, Information Processing Letters, 95 (2005)
503-511.
[10] W. Pullan, Phased local search for the maximum clique problem, J.
Comb. Optim. 12 (2006) 303-323.
[11] D. S. Johnson, M. A. Trick (Eds.): Cliques, Coloring and sats£ability,
Second DIMACS Implementation Challenge, DIMACS Series in Discrete
Mathematics and Theoretical Computer Science, Vol. 26, American
Mathematical Society, Providence, RI, 1996.
[12] P. A. Pevzner, S.-H. Sze, Combinatorial approaches to £nding subtle
signals in DNA sequences, in proceedings of Eighth International Conference
on intelligent systems for Molecular Biology, AIAA Press, New
York, (2000) 269-278.
[13] Y. Ji, X. Xu, G. D. Stormo, A graph theoretical approach for predicting
common RNA secondary structure motifs including pseudoknots in
unaligned sequences. Bioinformatics 20(10) (2004) 1591-1602.
[14] M. R. Garey, D. S. Johnson: Computers and Intractability: A Guide to
the theory NP - completeness. San Francisco: Freeman (1979).
[15] J. Hastad: Clique is hard to approximate within n1- , Acta Mathematica,
182 (1999) 105-142.
[16] R. Boppana, M. Halldorsson, Approximating maximum independent sets
by excluding subgraphs. Bit 32 (1992) 180-196.
[17] X. Geng, J. Xu, J. Xiao and L. Pan: A simple simulated annealing
algorithm for the Maximum Clique problem”, 177 (2007) 5064-5071.
[18] E. Tomita, T. Kameda, An ef£cient branch-and-bound algorithm for
£nding a maximum clique with computational experiments, J. Glob.
Optim. 37 (2007) 95-111.
[19] P. R. J. Ostergard: A fast algorithm for the maximum clique problem,
Discrete Applied Mathematics, 120 (2002) 197-207.
[20] E. Balas, W. Niehaus, Optimized crossover-Based Genetic Algorithm
for the Maximum Cardinality and Maximum Weight Clique Problems,
Journal of Heuristics, 4 (1998) 107-122.
[21] S. Busygin, A new trust region technique for the maximum weight clique
problem, Discrete Applied Mathematics, 154 (2006) 2080-2096.
[22] G. -Marin, E. -Casermeiro, J. -Perez, Modelling competitive Hop£eld
networks for the maximum clique problem, Computers & Operations
Research, 30 (2003) 603-624.
[23] W. Pullan, H. H. Hoos, Dynamic local search for the maximum clique
problem, Journal of Arti£cial Intelligence Research, 25 (2006) 159-185.
[24] W. Pullan, Approximating the maximum vertex/edge weighted clique
using local search, J. Heuristics, 14 (2008) 117-134.
[25] P. J. Taillon, A new approach for solving the maximum clique problem,
LNCS, Springer-Verlag Berlin Heidelberg, 4041 (2006) 279-290.
[26] V. C. Barbosa, C. D. Campos, A novel evolutionary formulation of the
maximum independent set problem, J. Comb. Optim. 8 (2004) 419-437.
[27] B. Alidaee, G. Kochenberger, H. Wang, Simple and fast surrogate constraint
heuristics for the maximum independent set problem, J. Heuristics,
14 (2008) 571-585.
[28] T. S. Feo, M. G. C. Resende, S. H. Smith, A greedy randomized adaptive
search procedure for maximum independent set, Operations Research,
42(5) (1994) 860-978.
[29] S. Balaji, V. Swaminathan, K. Kannan: Approximating maximum
weighted independent set using vertex Support, International Journal of
Computational and Mathemtical Sciences1, 3(8) (2009) 406-411.
[30] S. Balaji, N. Revathi: An Ef£cient approach for the Optimization
version of Maximum Weighted Clique Problem, WSEAS Transactions
on Mathematics, 11(9) (2012) 773-783.</p>
@article{"International Journal of Engineering, Mathematical and Physical Sciences:56811", author = "S. Balaji", title = "A New Effective Local Search Heuristic for the Maximum Clique Problem", abstract = "An edge based local search algorithm, called ELS, is proposed for the maximum clique problem (MCP), a well-known combinatorial optimization problem. ELS is a two phased local search method effectively £nds the near optimal solutions for the MCP. A parameter ’support’ of vertices de£ned in the ELS greatly reduces the more number of random selections among vertices and also the number of iterations and running times. Computational results on BHOSLIB and DIMACS benchmark graphs indicate that ELS is capable of achieving state-of-the-art-performance for the maximum clique with reasonable average running times.
", keywords = "Maximum clique, local search, heuristic, NP-complete.", volume = "7", number = "5", pages = "844-7", }
