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.

  • $\begingroup$ Why do you want to show this ? $\endgroup$ May 20, 2014 at 21:33
  • $\begingroup$ To show that APX is a proper subset of NPO. $\endgroup$ May 21, 2014 at 4:15
  • $\begingroup$ I mean, do you need it for a paper, or a presentation, or ... ? $\endgroup$ May 21, 2014 at 6:52
  • $\begingroup$ I need it for learning purposes. But primarily I would need a hint how to start with the subject. $\endgroup$ May 21, 2014 at 8:13
  • $\begingroup$ Reduce a Log-APX hard, Poly-APX hard, Exp-APX hard, or NPO hard problem into that problem, and you'll prove that it cannot be in APX as long as P != NP. $\endgroup$ Oct 16, 2017 at 22:12


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.