0
$\begingroup$

I have proposed an approximation algorithm for VCP that may produce a less than 2 approximation ratio. I know this contradicts what experts believe about the Unique Games Conjecture. However, I was hoping that experts could review my paper and identify any potential issues. Since last year and due to some of the answers in https://academia.stackexchange.com/questions/18491/i-believe-i-have-solved-a-famous-open-problem-how-do-i-convince-people-in-the-f

  1. I put my proof aside completely for one month without thinking about it. Then I rechecked it and tried to make my argument more convincing by introducing an easy-to-read short error-free convincing good-level explanation of my approach.
  2. Due to the endorsement of one of my co-authors I published it on arXiv. See https://arxiv.org/abs/2403.19680
  3. I submitted the paper to some conferences, journals, and experts.
  4. I tried to work on other problems and publish another paper. e.g. "Optimality of DSatur algorithm on chordal graphs". See https://www.sciencedirect.com/science/article/abs/pii/S0167637724001214

However, I have not received any comments yet. Then, I would appreciate it if anyone could read the paper and quote his/her answer/opinion.

My idea is as follows:

Theorem 1. If we have a lower bound on the VCP optimal value and we know $z_{VCP}^*\geq\frac{n}{2}+\frac{n}{k}=\frac{(k+2)n}{2k}$. Then, for all vertex cover feasible partitioning $V=V_1\cup V_0$, we have the approximation ratio $\frac{\mid V_1 \mid }{z_{VCP}^*}\leq \frac{2k}{k+2}<2$.

Theorem 2. If $z_{VCP}^*\geq\frac{n}{2}$ and we have produced a VCP feasible partitioning $V=V_1\cup V_0$, where $\mid V_1 \mid\leq k\mid V_0 \mid$, then, based on such a solution we have an approximation ratio $\frac{\mid V_1 \mid}{z_{VCP}^*}\leq\frac{2k}{k+1}<2$.

Then, to find a suitable lower bound (and apply Theorem 1) or a suitable solution (and apply Theorem 2), I introduce new graph $G2=(V_{new},E_{new})$ based on the connection of two copies of graph $G\ (G'=G"=G)$, where each vertex in $G'$ (one copy of $G$) is connected to all vertices of $G"$ (the other copy of $G$). Then, based on the known SDP model, I introduce a new SDP model as follows:

$$min_{s.t.}⁡z=\sum_{i\in V_{new}} X_{oi}$$ $$SDP\ \ constraints\ on\ G'\ and\ G"$$ $$ 0\leq X_{ij}\leq +1\ \ \ i,j\in V'\cup\{o\}\ \ \ or\ \ \ i,j\in V"\cup\{o\}$$ $$X_{oi}+X_{oj}-X_{ij}=1\ \ \ i\in V',\ j\in V"$$ $$-1\leq X_{ij}\leq +1\ \ \ i\in V', \ j\in V"$$ $$X\succeq 0$$

$\endgroup$
4
  • 1
    $\begingroup$ I think reviewing a paper is likely to be beyond the scope of this site. We're looking for questions that can be understood and answered in a few paragraphs. $\endgroup$ Commented Nov 12, 2024 at 23:14
  • $\begingroup$ @D.W. Definitly, I agree with you. I did it after I had done every thing else. When, after 6 months reviewer say "no one accept to review it" or experts say "I don't have time to find mistakes of it", I should think about another way. When journals don't accept to review the paper and experts don't like to say anything about it in private Email, I prefered to ask about it in an expertise forum like CS. Maybe, I will understand mistakes of my approach or my (improvement) idea can solve a famous open problem. $\endgroup$ Commented Nov 13, 2024 at 4:17
  • $\begingroup$ I'm afraid that even if you've done everything else you can think of, that doesn't make the question any more on-topic or suitable here. Our scope is limited. $\endgroup$ Commented Nov 13, 2024 at 18:26

0

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.