How can I show that zero-one programming is not in APX?
Vertex Cover Problem is in the APX class. So can I try a PTAS-reduction from the zero-one programming problem to Vertex Cover and show that there is no reduction between these problems?
Where to begin with?
- Does someone maybe know a paper with a similar topic?
I would be grateful for any advice.