2
$\begingroup$

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.

Improve this question
$\endgroup$
9
  • 2
    $\begingroup$ Chromatic number, that is minimizing the number of colors needed to color a graph. $\endgroup$
    – Chandra Chekuri
    Oct 12, 2017 at 1:45
  • 1
    $\begingroup$ 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. $\endgroup$
    – Chandra Chekuri
    Oct 12, 2017 at 14:29
  • 2
    $\begingroup$ 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. $\endgroup$
    – Yonatan N
    Oct 13, 2017 at 6:16
  • 2
    $\begingroup$ 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. $\endgroup$
    – Hermann Gruber
    Oct 24, 2017 at 20:46
  • 1
    $\begingroup$ 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). $\endgroup$
    – EXPTIME-complete
    Oct 25, 2017 at 6:37

1 Answer 1

Reset to default
1
$\begingroup$

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).

Improve this answer
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.