<p>How can I show that zero-one programming is not in APX?</p>

<ul>
<li><p>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? </p></li>
<li><p>Where to begin with?</p></li>
<li>Does someone maybe know a paper with a similar topic?</li>
</ul>

<p>I would be grateful for any advice.</p>

CC BY-SA 3.0
2014-05-20T21:33:33.303Z
Why do you want to show this ?
Suresh Venkat
CC BY-SA 3.0
2014-05-21T04:15:22.873Z
To show that APX is a proper subset of NPO.
user3615395
CC BY-SA 3.0
2014-05-21T06:52:26.123Z
I mean, do you need it for a paper, or a presentation, or ... ?
Suresh Venkat
CC BY-SA 3.0
2014-05-21T08:13:43.093Z
I need it for learning purposes. But primarily I would need a hint how to start with the subject.
user3615395
CC BY-SA 3.0
2017-10-16T22:12:58.550Z
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.
EXPTIME-complete
<approximation-algorithms><approximation-hardness><approximation><apx>
How can I show that zero-one programming is not in APX?
user3615395
# How can I show that zero-one programming is not in APX?

(Asked by: username_0 on 2014-05-20)

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.

**Tags:** approximation-algorithms, approximation-hardness, approximation, apx

> **Comments:**
> **username_1**: Why do you want to show this ?  
> **username_0**: To show that APX is a proper subset of NPO.  
> **username_1**: I mean, do you need it for a paper, or a presentation, or ... ?  
> **username_0**: I need it for learning purposes. But primarily I would need a hint how to start with the subject.  
> **username_2**: 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.  

---

## 0 answers

