<p>I've just discovered there exists at least one confirmed minimization Poly-APX-complete problem: Min ones if setting all variables true satisfies all clauses (together with other conditions). It is shown in "The Approximability of Constraint Satisfaction
Problems" by Sanjeev Khannay, Madhu Sudanz, Luca Trevisanx and David P. Williamson (<a href="http://people.csail.mit.edu/madhu/papers/2001/kstw.pdf" rel="nofollow noreferrer">http://people.csail.mit.edu/madhu/papers/2001/kstw.pdf</a>), Theorem 2.14, item (5).</p>

CC BY-SA 3.0
2017-11-15T20:48:53.657Z
2017-11-16T00:13:28.700Z
2017-11-16T00:13:28.700Z
EXPTIME-complete
<p>All Poly-APX-complete problems I know are maximization problems, e.g. Max Clique, Max Independent Set, Max One for some set of contraints, and even choosing the attributes of a product to maximize (Max again!) the number of customers preferring it, provided that preferences are additive (<a href="http://www.sciencedirect.com/science/article/pii/S1568494617300510" rel="nofollow noreferrer">http://www.sciencedirect.com/science/article/pii/S1568494617300510</a>). Max, max, max... Is there any known Poly-APX-complete Min problem?</p>

<p>I suspect a problem I'm dealing with might be Poly-APX-complete, but it's a minimization problem. If there were some known Poly-APX-complete Min problem, an AP-reduction from it into my target problem would map Min into Min, so proving the Poly-APX-hardness of my target problem would probably be more natural and easier.</p>

CC BY-SA 3.0
2017-10-12T01:45:48.353Z
Chromatic number, that is minimizing the number of colors needed to color a graph.
Chandra Chekuri
CC BY-SA 3.0
2017-10-12T10:59:10.250Z
Thanks! By googling "graph coloring poly-apx-complete", I've found the following related question: https://cstheory.stackexchange.com/questions/25297/is-graph-coloring-complete-for-poly-apx. However, after checking the paper mentioned in Edit 1, I'm afraid I have the same objection as the author of that question. Has the Poly-APX-completeness of graph coloring ever been clearly stated?
EXPTIME-complete
CC BY-SA 3.0
2017-10-12T14:29:41.307Z
Note sure completeness is really useful concept here. If you want to prove that your problem is hard simply use an existing hard problem and a reduction.
Chandra Chekuri
CC BY-SA 3.0
2017-10-12T17:07:52.440Z
But I should use a reduction from a problem whose approximability matches the one I want to prove, right? If I'm right and my target problem turns out to be Poly-APX-complete, then I won't be able to AP-reduce an Exp-APX problem into it (even though Exp-APX hardness implies Poly-APX hardness). On the other hand, reducing a Log-APX problem into it would not prove the Poly-APX hardness of the target problem. Thus I need to use a Poly-APX-complete problem, that is, a Poly-APX hard problem whose approximability cannot be worse than Poly-APX. Is there any other better way?
EXPTIME-complete
CC BY-SA 3.0
2017-10-13T06:16:05.223Z
Often, one cares less about proving completeness for a problem than for showing the intractability of it. For example, if P !=NP then showing intractability by reducing from the non-NP-hard problem highlighted in Ladner's theorem would do you just as well as reducing from SAT (in terms of ruling out polytime solutions). While I don't know whether chromatic number is hard under the types of reductions you care about, it's known that it's extremely hard to approximate assuming P != NP, and this hardness carries through to any problem from which you can form an approximation-preserving reduction.
Yonatan N
CC BY-SA 3.0
2017-10-13T21:14:49.043Z
Interesting point. Anyway, completeness is a useful goal by itself, as it shows you that (a) your problem can be approximated with some quality (e.g. with a Poly-APX approximation if it is in Poly-APX); and (b) it cannot be approximated "much better" if P != NP. If you get (a) and (b), then your approximation is "optimal" in a "wide" sense (e.g. polynomial vs exponential vs logarithmic; though you could still improve e.g. the constant k of your O(n^k) Poly-APX approximation).
EXPTIME-complete
CC BY-SA 3.0
2017-10-13T21:17:00.383Z
By the way, today I found a sub-polynomial (n / log n) approximation for my target problem, so I should rule out its Poly-APX hardness (or accept the possibility of a huge surprise!). I already proved its Log-APX hardness, so I'll spend some time looking for a Log-APX approximation. I'm still very interested in my original question though, for the sake of my future classification efforts (it's not the first time I wish a could use some Poly-APX-complete minimization problem to prove Poly-APX hardness).
EXPTIME-complete
CC BY-SA 3.0
2017-10-24T20:46:45.863Z
Regarding your previous comment, I think that poly-APX-hardness implies hardness of approximation in $n^\epsilon$ for some $\epsilon>0$ (and not for $\epsilon \geq 1$). So your problem can still be hard for poly-APX even if there exists a $n/\log n$ approximation algorithm.
Hermann Gruber
CC BY-SA 3.0
2017-10-25T06:37:30.343Z
Very good point! I was ignoring that possibility. Now, having a (proved) min Poly-APX-complete problem to try an AP-reductrion would be very nice (as I couldn't find any way to do it from any max Poly-APX-complete problem).
EXPTIME-complete
<reference-request><complexity-classes><approximation-hardness><approximation>
Is there any known Poly-APX-complete minimimization problem?
EXPTIME-complete
# Is there any known Poly-APX-complete minimimization problem?

(Asked by: username_0 on 2017-10-12)

All Poly-APX-complete problems I know are maximization problems, e.g. Max Clique, Max Independent Set, Max One for some set of contraints, and even choosing the attributes of a product to maximize (Max again!) the number of customers preferring it, provided that preferences are additive (<http://www.sciencedirect.com/science/article/pii/S1568494617300510>). Max, max, max... Is there any known Poly-APX-complete Min problem?

I suspect a problem I'm dealing with might be Poly-APX-complete, but it's a minimization problem. If there were some known Poly-APX-complete Min problem, an AP-reduction from it into my target problem would map Min into Min, so proving the Poly-APX-hardness of my target problem would probably be more natural and easier.

**Tags:** reference-request, complexity-classes, approximation-hardness, approximation
> **Comments:**
> **username_1**: Chromatic number, that is minimizing the number of colors needed to color a graph.  
> **username_0**: Thanks! By googling "graph coloring poly-apx-complete", I've found the following related question: https://cstheory.stackexchange.com/questions/25297/is-graph-coloring-complete-for-poly-apx. However, after checking the paper mentioned in Edit 1, I'm afraid I have the same objection as the author of that question. Has the Poly-APX-completeness of graph coloring ever been clearly stated?  
> **username_1**: Note sure completeness is really useful concept here. If you want to prove that your problem is hard simply use an existing hard problem and a reduction.  
> **username_0**: But I should use a reduction from a problem whose approximability matches the one I want to prove, right? If I'm right and my target problem turns out to be Poly-APX-complete, then I won't be able to AP-reduce an Exp-APX problem into it (even though Exp-APX hardness implies Poly-APX hardness). On the other hand, reducing a Log-APX problem into it would not prove the Poly-APX hardness of the target problem. Thus I need to use a Poly-APX-complete problem, that is, a Poly-APX hard problem whose approximability cannot be worse than Poly-APX. Is there any other better way?  
> **username_2**: Often, one cares less about proving completeness for a problem than for showing the intractability of it. For example, if P !=NP then showing intractability by reducing from the non-NP-hard problem highlighted in Ladner's theorem would do you just as well as reducing from SAT (in terms of ruling out polytime solutions). While I don't know whether chromatic number is hard under the types of reductions you care about, it's known that it's extremely hard to approximate assuming P != NP, and this hardness carries through to any problem from which you can form an approximation-preserving reduction.  
> **username_0**: Interesting point. Anyway, completeness is a useful goal by itself, as it shows you that (a) your problem can be approximated with some quality (e.g. with a Poly-APX approximation if it is in Poly-APX); and (b) it cannot be approximated "much better" if P != NP. If you get (a) and (b), then your approximation is "optimal" in a "wide" sense (e.g. polynomial vs exponential vs logarithmic; though you could still improve e.g. the constant k of your O(n^k) Poly-APX approximation).  
> **username_0**: By the way, today I found a sub-polynomial (n / log n) approximation for my target problem, so I should rule out its Poly-APX hardness (or accept the possibility of a huge surprise!). I already proved its Log-APX hardness, so I'll spend some time looking for a Log-APX approximation. I'm still very interested in my original question though, for the sake of my future classification efforts (it's not the first time I wish a could use some Poly-APX-complete minimization problem to prove Poly-APX hardness).  
> **username_3**: Regarding your previous comment, I think that poly-APX-hardness implies hardness of approximation in $n^\epsilon$ for some $\epsilon>0$ (and not for $\epsilon \geq 1$). So your problem can still be hard for poly-APX even if there exists a $n/\log n$ approximation algorithm.  
> **username_0**: Very good point! I was ignoring that possibility. Now, having a (proved) min Poly-APX-complete problem to try an AP-reductrion would be very nice (as I couldn't find any way to do it from any max Poly-APX-complete problem).  

---

## 1 answers

### Answer by username_0 on 2017-11-15. Score: 1 | Accepted answer

I've just discovered there exists at least one confirmed minimization Poly-APX-complete problem: Min ones if setting all variables true satisfies all clauses (together with other conditions). It is shown in "The Approximability of Constraint Satisfaction
Problems" by Sanjeev Khannay, Madhu Sudanz, Luca Trevisanx and David P. Williamson (<http://people.csail.mit.edu/madhu/papers/2001/kstw.pdf>), Theorem 2.14, item (5).


---

