A Meta-Heuristic Algorithm for Vertex Covering Problem Based on Gravity

A new Meta heuristic approach called "Randomized gravitational emulation search algorithm (RGES)" for solving vertex covering problems has been designed. This algorithm is found upon introducing randomization concept along with the two of the four primary parameters -velocity- and -gravity- in physics. A new heuristic operator is introduced in the domain of RGES to maintain feasibility specifically for the vertex covering problem to yield best solutions. The performance of this algorithm has been evaluated on a large set of benchmark problems from OR-library. Computational results showed that the randomized gravitational emulation search algorithm - based heuristic is capable of producing high quality solutions. The performance of this heuristic when compared with other existing heuristic algorithms is found to be excellent in terms of solution quality.

• S. Raja Balachandar
• K.Kannan

• Vertex covering Problem
• Velocity
• Gravitational Force
• Newton's Law
• Meta Heuristic
• Combinatorial optimization.

[1] Bollobas. B : Random graphs (2nd Ed.). Cambridge, UK: Cambridge
University press, 2001.
[2] Berman. P and Fujito. T: On approximation properties of the independent
set problem for low degree graphs, Theory of Computing Syst., vol. 32,
pp. 115 - 132, 1999.
[3] Chvatal, V. (1979). "A Greedy-Heuristic for the Set Cover Problem."
Mathematics of Operations Research 4, 233-235.
[4] Clarkson, K.L (1983). "A Modification of the Greedy Algorithm for
Vertex Cover." Information Processing Lettters 16, 23-25.
[5] Cormen. T. H, C. E. Leiserson, R. L. R., and Stein. C: Introduction to
algorithms, 2nd ed., McGraw - Hill, New York , 2001.
[6] Dehne. F, et al.: Solving large FPT problems on coarse grained parallel
machines, Available: http://www.scs.carleton.ca/fpt/papers/index.htm.
[7] Fellows. M. R: On the complexity of vertex cover problems, Technical
report, Computer science department, University of New Mexico, 1988.
[8] Garey. M. R, Johnson. D. S: Computers and Intractability: A Guide to
the theory NP - completeness. San Francisco: Freeman ,1979.
[9] Garey. M. R, Johnson. D. S, and Stock Meyer. L: Some simplified NP
- complete graph problems, Theoretical computer science, Vol.1563, pp.
561 - 570, 1999.
[10] Glover. F: Tabu Search - Part I, ORSA journal of computing, vol. 1,
No.3, (1989), pp. 190 - 206.
[11] Glover. F: Tabu search: A Tutorial, Interface 20, pp. 74 - 94, 1990.
[12] Gomes. F. C, Meneses. C. N, Pardalos. P. M and Viana. G. V. R: Experimental
analysis of approximation algorithms for the vertex cover and set
covering problems, Journal of computers and Operations Research, vol.
33, pp. 3520 - 3534, 2006.
[13] Hastad. J: Some Optimal Inapproximability Results., Journal of the
ACM, vol. 48, No.4, pp. 798 - 859, 2001.
[14] Hochbaum. D. S: Approximation algorithm for the set covering and
vertex cover problems, SIAM Journal on computing, 11(3), 555 - 6, 1982.
[15] D. Holliday, R. Resnick, J. Walker, Fundamentals of physics, John Wiley
and Sons, 1993.
[16] Johnson. D.S, Approximation Algorithms for Combinatorial problems,
J.Comput.System Sci.9(1974)256-278.
[17] Johnson, D.s., C.R Aragon, L.A. McGeoch, and C. Schevon. (1989).
"Optimization by Simulated Anealing: An Experimental Evaluation, Part
I: Graph Partitioning." Operations Research 37, 875-892.
[18] Johnson, D.S., C.R. Aragon, L.A. McGeoch, and C.Schevon. (1989b).
"Optimization by Simulated Annealing: An Experimental Evaluation, part
II: Graph Coloring and Number Partitioning." Operations Research 39,
378-406.
[19] Karp. R. M: Reducibility among combinatorial problems, Plenum Press,
New York, pp. 85 - 103, 1972.
[20] I.R. Kenyon, General Relativity, Oxford University Press, 1990.
[21] Khuri S, Back Th. An Evolutionary heuristic for the minimum vertexcover
problem. 18th Deutche Jahrestagung fur Kunstliche. Max-Planck
Institut fur Informatik Journal 1994;MPI-I-94-241:86-90.
[22] Likas, A and Stafylopatis, A: A parallel algorithm for the minimum
weighted vertex cover problem, Information Processing Letters, vol. 53,
pp. 229 - 234, 1995.
[23] R. Mansouri, F. Nasseri, M. Khorrami, Effective time variation of G
in a model universe with variable space dimension, Physics Letters 259
(1999) 194-200.
[24] Motwani, R. (1992). "Lecture Notes on Application. " Technical Report,
STAN-CS-92-1435, Department of Computer Science, Stanford University.
[25] Motwani. R: Lecture Notes on Approximation Algorithms, Technical
Report, STAN-CS-92-1435, Department of Computer Science, Stanford
University, 1992.
[26] Neidermeier. R and Rossmanith. P: On efficient fixed-parameter algorithms
for weighted vertex cover, Journal of Algorithms, vol. 47, pp. 63
- 77, 2003.
[27] Pitt. L: A Simple Probabilistic Approximation Algorithm for Vertex
Cover, Technical Report, YaleU/DCS/TR-404, Department of Computer
Science, Yale University, 1985.
[28] E. Rashedi, Gravitational Search Algorithm, M.Sc. Thesis, Shahid
Bahonar University of Kerman, Kerman, Iran, 2007 (in Farsi).
[29] B. Schutz, Gravity from the Ground Up, Cambridge University Press,
2003.
[30] Monien. B and Speckenmeyer. E: Ramsey numbers and an approximation
algorithm for the vertex cover problems, Acta Informatica, vol. 22,
pp. 115 - 123, 1985.
[31] Shyu. S.J, Yin. P.Y and Lin. B.M.T: An ant colony optimization
algorithm for the minimum weight vertex cover problem, Annals of
Operations Research, Vol. 131, pp. 283 - 304, 2004.
[32] Weight. M and Hartmann. A. K: The number of guards needed by a
museum - a phase transition in vertex covering of random graphs., Phys
- Rev. Lett., 84, 6118, 2000b.
[33] Weight. M and Hartmann. A. K.: Minimal vertex covers on finite
connectivity random graphs - A hard-sphere lattice-gas picture, Phys.
Rev. E, 63, 056127.