Skip to main content
SpringerLink
Log in

An Ant Colony Optimization Algorithm for the Minimum Weight Vertex Cover Problem

  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

Given an undirected graph and a weighting function defined on the vertex set, the minimum weight vertex cover problem is to find a vertex subset whose total weight is minimum subject to the premise that the selected vertices cover all edges in the graph. In this paper, we introduce a meta-heuristic based upon the Ant Colony Optimization (ACO) approach, to find approximate solutions to the minimum weight vertex cover problem. In the literature, the ACO approach has been successfully applied to several well-known combinatorial optimization problems whose solutions might be in the form of paths on the associated graphs. A solution to the minimum weight vertex cover problem however needs not to constitute a path. The ACO algorithm proposed in this paper incorporates several new features so as to select vertices out of the vertex set whereas the total weight can be minimized as much as possible. Computational experiments are designed and conducted to study the performance of our proposed approach. Numerical results evince that the ACO algorithm demonstrates significant effectiveness and robustness in solving the minimum weight vertex cover problem.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Alimonti, P. and V. Kann. (2000). “Some APX-Completeness Results for Cubic Graphs.” Theoretical Computer Science 237, 123-134.

    Article  Google Scholar 

  • Balasubramanian, R., M.R. Fellows, and V. Raman. (1998). “An Improved Fixed-Parameter Algorithm for Vertex Cover.” Information Processing Letters 65, 163-168.

    Article  Google Scholar 

  • Bar-Yehuda, R. and S. Even. (1985). “A Local-Ratio Theorem for Approximating with theWeighted Vertex Cover Problem.” Annals of Discrete Mathematics 25, 27-45.

    Google Scholar 

  • Bullnheimer, B., R.F. Hartl, and C. Strauss. (1999). “A New Rank-Based Version of the Ant System: A Computational Study.” Central European Journal of Operations Research and Economics 7, 25-38.

    Google Scholar 

  • Chen, J., I.A. Kanj, and W. Jia. (1999). “Vertex Cover: Further Observations and Further Improvements.” In The 25th International Workshop on Graph-Theoretical Concepts in Computer Science.

  • Clarkson, K.L. (1983). “AModification of the Greedy Algorithm for Vertex Cover.” Information Processing Letters 16, 23-25.

    Article  Google Scholar 

  • Chvatal, V. (1979). “A Greedy-Heuristic for the Set Cover Problem.” Mathematics of Operations Research 4, 233-235.

    Google Scholar 

  • Colorni, A.,M. Dorigo, and V. Maniezzo. (1991). “Distributed Optimization by Ant Colonies.” In Proceedings of European Conference on Artificial Life, Paris, France. Elsevier Science Publishing, pp. 134-142.

    Google Scholar 

  • Costa, D. and A. Hertz. (1997). “Ants Can Color Graphs.” Journal of the Operational Research Society 48, 295-305.

    Article  Google Scholar 

  • Dinur, I. and S. Safra. (2001). “The Importance of Being Biased.” Technical Report, Department of Computer Science, Tel Aviv University, Israel.

    Google Scholar 

  • Dorigo, M., E. Bonabeau, and G. Theraulaz. (2000). “Ant Algorithm and Stigmergy.” Future Generation Computer Systems 16, 851-871.

    Google Scholar 

  • Dorigo, M., G.D. Caro, and L.M. Gambardella. (1999). “Ant Algorithms for Optimization.” Artificial Life 5(3), 137-72.

    Google Scholar 

  • Dorigo, M. and L.M. Gambardella. (1997a). “Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem.” IEEE Transactions on Evolutionary Computation 1(1), 53-66.

    Article  Google Scholar 

  • Dorigo, M. and L.M. Gambardella. (1997b). “Ant Colonies for the Traveling Salesman Problem.” BioSystems 43, 73-81.

    Article  Google Scholar 

  • Dorigo, M., V. Maniezzo, and A. Colorni. (1991). “Positive Feedback as a Search Strategy.” Technical Report, 91-016, Politecnico idi Milano.

  • Dorigo, M., V. Maniezzo, and A. Colorni. (1996). “The Ant System: Optimization by a Colony of Cooperating Agents.” IEEE Transactions on Systems, Man, and Cybernetics — Part B 26(1), 29-41.

    Google Scholar 

  • Downey, R.G. and M.R. Fellows. (1995a). “Fixed-Parameter Tractability and Completeness I: Basic Results.” SIAM Journal on Computing 24, 873-921.

    Article  Google Scholar 

  • Downey, R.G. and M.R. Fellows. (1995b). “Parameterized Computational Feasibility.” In P. Clote and J. Remmel (eds.), Feasible Mathematics, Vol. II. Boston, pp. 219-244.

  • Feige, U. (1998). “A Threshold of ln nfor Approximating Set Cover.” Journal of the ACM 45(4), 634-652.

    Article  Google Scholar 

  • Gambardella, L.M. and M. Dorigo. (1995). “Ant-Q: A Reinforcement Learning Approach to the Traveling Salesman Problem.” In A. Prieditis and S. Russell (eds.), Proceedings of the Twelfth International Conference on Machine Learning, ML-95, Tahoe City, CA. Morgan Kaufmann, pp. 252-260.

    Google Scholar 

  • Garey, M.R. and D.S. Johnson. (1979). Computers and Intractability: A Guide to the Theory of NPCompleteness. San Francisco, CA: W.H. Freeman.

    Google Scholar 

  • Glover, F. (1989). “Tabu Search — Part I.” ORSA Journal on Computing 1(3), 190-206.

    Google Scholar 

  • Glover, F. (1990). “Tabu Search: A Tutorial.” Interface 20, 74-94.

    Google Scholar 

  • Hastad, J. (2001). “Some Optimal Inapproximability Results.” Journal of the ACM 48(4), 798-859.

    Google Scholar 

  • Jayaraman, V.K., B.D. Kulkarni, S. Karale, and P. Shelokar. (2000). “Ant Colony Framework for Optimal Design and Scheduling of Batch Plants.” Computers and Chemical Engineering 24, 1901-1912.

    Article  Google Scholar 

  • Johnson, D.S., C.R. Aragon, L.A. McGeoch, and C. Schevon. (1989a). “Optimization by Simulated Annealing: An Experimental Evaluation, Part I: Graph Partitioning.” Operations Research 37, 875-892.

    Google Scholar 

  • 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.

    Google Scholar 

  • Karp, R.M. (1972). “Reducibility Among Combinatorial Problems.” In R.E. Miller and J.W. Theater (eds.), Complexity of Computer Computations. New York: Plenum Press.

    Google Scholar 

  • Kirkpatrick, S., C.D. Gellatt, and M.P. Vechi. (1983). “Optimization by Simulated Annealing.” Science 220, 671-680.

    Google Scholar 

  • Maniezzo, V. (1998). “Exact and Approximate Non-Deterministic Tree-Search Procedures for the Quadratic Assignment Problem.” Research Report CSR 98-1, Scienze dell'Informazione, University Di Bologna, Sede Di Cesena, Italy.

    Google Scholar 

  • Monien, B. and E. Speckenmeyer. (1985). “Ramsey Numbers and an Approximation Algorithm for the Vertex Cover Problem.” Acta Informatica 22, 115-123.

    Article  Google Scholar 

  • Motwani, R. (1992). “Lecture Notes on Approximation Algorithms.” Technical Report, STAN-CS-92-1435, Department of Computer Science, Stanford University.

    Google Scholar 

  • Niedermeter, R. and P. Rossmanith. (1999). “Upper Bounds for Vertex Cover Further Improved.” In Proc. of STACS'99, Lecture Notes in Computer Science, Vol. 1536, pp. 561-570.

    Google Scholar 

  • Paschos, V.T. (1997). “A Survey of Approximately Optimal Solutions to Some Covering and Packing Problems.” ACM Computing Surveys 29(2), 171-209.

    Article  Google Scholar 

  • Pitt, L. (1985). ”A Simple Probabilistic Approximation Algorithm for Vertex Cover.” Technical Report, YaleU/DCS/TR-404, Department of Computer Science, Yale University.

  • Shyu, S.J., B.M.T. Lin, and P.Y. Yin. (2001). “Application of Ant Colony Optimization for No-Wait Flowshop Scheduling Problem to Minimize the Total Completion Time.” Presented at the INFORMSMeeting, Maui, Hawaii, June.

  • Shyu, S.J., P.Y. Yin, B.M.T. Lin, and M. Haouari. (2003). “Ant-Tree: An Ant Colony System for the Generalized Minimum Spanning Tree Problem.” Journal of Experimental & Theoretical Artificial Intelligence 15(1), 103-112.

    Article  Google Scholar 

  • Stutzle, T. and H. Hoos. (1997). “Improvements on the Ant System: Introducing MAX-MIN Ant System.” In Proceedings of the International Conference on Artificial Neural Networks and Genetic Algorithms, Springer, pp. 245-249.

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science and Information Engineering, Ming Chuan University, Tao-Yuan, 333, Taiwan

    Shyong Jian Shyu

  2. Department of Information Management, National Chi Nan University, Nan-Tou, 545, Taiwan

    Peng-Yeng Yin & Bertrand M.T. Lin

Authors
  1. Shyong Jian Shyu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Peng-Yeng Yin
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Bertrand M.T. Lin
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Shyu, S.J., Yin, PY. & Lin, B.M. An Ant Colony Optimization Algorithm for the Minimum Weight Vertex Cover Problem. Ann Oper Res 131, 283–304 (2004). https://doi.org/10.1023/B:ANOR.0000039523.95673.33

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/B:ANOR.0000039523.95673.33

Search

Navigation