New insight into introducing a (2-\epsilon)-approximation ratio for minimum vertex cover problem
| Autor: | Zohrehbandian, Majid |
|---|---|
| Přispěvatelé: | Department of Mathematics, Karaj Branch, Islamic Azad University, Karaj, Iran., Zohrehbandian, Majid |
| Jazyk: | angličtina |
| Rok vydání: | 2021 |
| Předmět: |
[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO]
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC] Discrete Optimization [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] Vertex Cover Problem [INFO.INFO-CC] Computer Science [cs]/Computational Complexity [cs.CC] [MATH.MATH-OC] Mathematics [math]/Optimization and Control [math.OC] [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC] NP-Complete Problems ACM: G.: Mathematics of Computing/G.2: DISCRETE MATHEMATICS/G.2.1: Combinatorics/G.2.1.0: Combinatorial algorithms Complexity Theory |
| Popis: | Vertex cover problem is a famous combinatorial problem, which 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 on special graphs. Then, by introducing a modified graph and corresponding model along with satisfying the proposed assumptions, we propose new insight into solving this open problem and we introduce an approximation algorithm with a performance ratio of on arbitrary graphs. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|