I have a new idea (by a combination of a well-known SDP formulation and a randomized procedure) to introduce an approximation algorithm for the vertex cover problem (VCP) with a performance ratio of $2 - \epsilon$.
You can see the abstract of the idea in attached file and the last version of the paper in https://vixra.org/abs/2107.0045
I am grateful if anyone can give me informative suggestions.
Dear Majid Zohrehbandian,
I suggest you see the links on the topic.
Conference Paper New Approximation Algorithms for the Vertex Cover Problem
Conference Paper Approximation Algorithms for Edge Partitioned Vertex Cover Problems
Article Approximation Algorithm for N-distance Minimal Vertex Cover Problem
Preprint Reoptimization of Path Vertex Cover Problem
https://www.geeksforgeeks.org/vertex-cover-problem-set-1-introduction-approximate-algorithm-2/
https://cpsc.yale.edu/sites/default/files/files/tr404.pdf
Best regards
Dear Mohamed-Mourad Lafifi ,
Thank you for your suggestions.
But, my request was about identifying any potential issues in my idea.
Since, I read some of these papers and as you know (and mentioned in most papers) the Unique Games Conjecture states that there is no c-approximation polynomial algorithm for VCP with c a constant strictly less than 2.
Indeed, all of approximation algorithms in research papers (for example the first paper you mentioned: New Approximation Algorithms for the Vertex Cover Problem) have an approximation ratio stricly less than 2 (but non constant or only on special graphs).
My claim is that my algorithm produce a constant ratio (1.999999) less than 2. But, I have a problem that the review process of reviewers (of a conference and a journal) were unfair and they reject my paper without mentioning any basic error.
For example, They said that:
1. It seems to me that the relevant board members were skeptical of the correctness of this submission, but found it too imposing to detect an error in it. 2. The submission uses a standard SDP relaxation which I believe already has an integrality gap of 2-o(1) (so there is likely to be an error somewhere in his rounding and analysis). 3. There doesn't seem to be any striking claim anywhere, especially of combinatorial, structural graph theoretic nature, and I doubt one can get such a stunning result without it. 4. The results of the paper cannot be true since they are ruled out by previous works. Strong integrality gaps, which rule out such a rounding, are known to exist for this SDP.
While, I said that I produce the ratio by solving an SDP formulation and a randomized procedure. However, I am sure (99%) that it is true.
Then, I am grateful if anyone can take the time to read the paper and identify any potential issues and informative suggestions.
Best regards
- Badges
- Science topic
- Similar topics
- Mathematical Sciences
- Graphs