A ($2-\varepsilon$)-approximation ratio for vertex cover problem on special graphs
الموضوعات :
N. Yekezare
1
,
M. Zohrehbandian
2
,
M. Maghasedi
3
1 - Department of Mathematics, Karaj Branch, Islamic Azad University, Karaj, Iran
2 - Department of Mathematics, Karaj Branch, Islamic Azad University, Karaj, Iran
3 - Department of Mathematics, Karaj Branch, Islamic Azad University, Karaj, Iran
الکلمات المفتاحية: Discrete optimization, Vertex cover problem, Complexity theory,
ملخص المقالة :
The vertex cover problem is a famous combinatorial problem, and its complexity has been heavily studied. It is known that it is hard to approximate to within any constant factor better than $2$, while a $2$-approximation for it can be trivially obtained. In this paper, new properties and new techniques are introduced which lead to approximation ratios smaller than $2$ on special graphs; e.g. graphs for which their maximum cut values are less than $0.999|E|$. In fact, we produce a ($1.9997$)-approximation ratio on graph $G$, where the ($0.878$)-approximation algorithm of the Goemans-Williamson for the maximum cut problem on $G$ produces a value smaller than $0.877122|E|$.
[1] D. Avis, T. Imamura, A list heuristic for vertex cover, Oper. Res. Lett. 35 (2007), 201-204.
[2] H. Bhasin, Harnessing genetic algorithm for vertex cover problem, Inter. J. Comput. Sci. Engin. 4 (2012), 218-223.
[3] V. Chvatal, A greedy heuristic for the set covering problem, Math. Oper. Res. 4 (3) (1979), 233-235.
[4] F. Delbot, C. Andlaforest, A better list heuristic for vertex cover, Inform. Proc. Lett. 107 (2008), 125-127.
[5] F. Delbot, C. Laforest, Analytical and experimental comparison of six algorithms for the vertex cover problem, ACM J. Experimental Algorithmics. 15 (2010), 1-26.
[6] I. Dinur, S. Safra, On the hardness of approximating minimum vertex cover, Annal. Math. 162 (2005), 439-485.
[7] M. Fayaz, S. Arshad, A. S. Shah, A. Shah, Approximate methods for minimum vertex cover fail to provide optimal results on small graph instances: A review, Inter. J. Control. Automation. 11 (2) (2018), 135-150.
[8] M. R. Garey, D. Andjohnson, Computers and Intractability, Freeman, New York, 1979.
[9] M. X. Goemans, D.P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. ACM. 42 (6) (1995), 1115-1145.
[10] R. Jovanovic, M. Tuba, An ant colony optimization algorithm with improved pheromone correction strategy for the minimum weight vertex cover problem, Appl. Soft. Comput. 11 (2011), 5360-5366.
[11] S. Khot, On the Power of Unique 2-Prover 1-Round Games, Proceeding of 34th ACM Symposium on Theory of Computing, STOC, 2002.
[12] S. Khot, O. Regev, Vertex cover might be hard to approximate to within 2−ε, J. Computer. System. Sciences. 74 (2008), 335-349.
[13] C. Savage, Depth-first search and the vertex cover problem, Inform. Proc. Lett. 14 (1982), 233-235.
[14] S. J. Shyu, P. Y. Yin, B. M. T. Lin, An ant colony optimization algorithm for the minimum weight vertex cover problem, Annal. Oper. Res. 131 (2004), 283-304.
[15] A. Singh, A. K. Gupta, A hybrid heuristic for the minimum weight vertex cover problem, Asia-Pacific J. Oper. Res. 23 (2006), 273-285.
[16] S. Voβ, A. Fink, A hybridized tabu search approach for the minimum weight vertex cover problem, J. Heuristics. 18 (2012), 869-876.
[17] C. Witt, Analysis of an iterated local search algorithm for vertex cover in sparse random graphs, Theore. Comput. Sci. 425 (2012), 117-125.
[18] X. Xu, J. Ma, An efficient simulated annealing algorithm for the minimum vertex cover problem, Neurocomputing. 69 (2006), 913-916.
