Open Access Open Access  Restricted Access Subscription or Fee Access

Complete Algorithms on Minimum Vertex -Cover

K. V. R. Kumar, Narendhar Maaroju, Dr. Deepak Garg

Abstract


The vertex cover problem is a classical NP-complete problem for which the best worst-case approximation ratio is 2 -o(1).This paper analyzes the hierarchical Bayesian optimization algorithm(hBOA) on minimum vertex cover for standard classes of random graphs. The performance of hBOA is compared with that of the branch-and-bound problem solver (BB), the simple genetic algorithm(GA) and the parallel simulated annealing (PSA). The results indicate that BB is significantly outperformed by all the other methods, which
is expected as BB is a complete search algorithm and minimum vertex cover is an NP-complete problem. The best performance is achieved with hBOA; nonetheless, the performance differences between hBOA and other evolutionary algorithms are relatively small, indicating that mutation-based search and recombination-based search lead to similar performance on problem instances.


Keywords


Minimum vertex cover, hierarchical BOA, genetic algorithm, simulated annealing, branch and bound.

Full Text:

PDF

References


T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms. McGraw-Hill, New York, 2nd edition, 2001.

X. Huang, J. Lai, and S. F. Jennings. Maximum common subgraph:Some upper bound and lower bound results. BMC Bioinformatics,7(Suppl 4):S6, 2006.

M.Pelikan. Hierarchical Bayesian optimization algorithm: Toward a new generation of evolutionary algorithms. Spr inger-Verlag, 2005.

R. Arakaki, and L. Lorena, “A Constructive Genetic Algorithm for the Maximal Covering Location Problem”, in Proceedings of Metaheuristics International Conference, 2001, pp 13-17.

S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi. Optimization by simulated annealing. Science, 220:671–680, 1983.

R. Luling and B. Monien. Load balancing for distributed branch and bound algorithms. In The 6th International Parallel Processing Symposium, pages 543–549, Los Alamitos, USA, 1992. IEEE Computer Society Press.

P. Erdos and A. Renyi. On the evolution of random graphs. Publ. Math.Inst. Hung. Acad. Sci., 5:17, 1960.

M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York, 1979.

M. Weigt and A. K. Hartmann. The number guards needed by a museum– a phase transition in vertex covering of random graphs. Phys. Rev.Lett., 84:6118, 2000.

M. Weigt and A. K. Hartmann. The typical-case complexity of a vertexcovering algorithm on finite-connectivity random graphs. Phys. Rev.Lett., 86:1658, 2001

K.Hartmann and M.Weigt.Phase Transitionsin Combinatorial Optimization Problems. Wiley-VCH, Weinheim, 2005.

Bollobas. Random Graphs. Cambridge University Press, Cambridge,UK, 2nd edition, 2001.

K. Sastry. Evaluation-relaxation schemes for genetic and evolutionary algorithms. Master’s thesis, University of Illinois at Urbana-Champaign,Department of General Engineering, Urbana, IL, 2001. Also IlliGAL Report No. 2002004.

Miroslav Chleb and Janka Chleb, “Crown reductions for the Minimum Weighted Vertex Cover problem” Electronic Colloquium on Computational Complexity, Report No. 101 (2004).

R. Bar-Yehuda and S. Even. A local-ratio theorem for approximating the weighted vertex cover problem. Annals of Discrete Mathematics, 25:27– 45, 1985.

M. Mezard, G. Parisi, and R. Zecchina. Analytic and algorithmic solution of random satisfiability problems. Science, 297:812, 2002.


Refbacks

  • There are currently no refbacks.