# Is there any known Poly-APX-complete minimimization problem?

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.

• Chromatic number, that is minimizing the number of colors needed to color a graph. Commented Oct 12, 2017 at 1:45
• 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. Commented Oct 12, 2017 at 14:29
• 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. Commented Oct 13, 2017 at 6:16
• 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. Commented Oct 24, 2017 at 20:46
• 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). Commented Oct 25, 2017 at 6:37