Search code examples
complexity-theoryapproximationnp-complete

What does this sentence mean "It is NP-hard to approximate the Max-3-DM with bound 2 "?


It has been shown that: it is NP-hard to approximate the maximum 3-dimensional matching problem (Max-3-DM) to within 95/94, this result apply to instances with exactly two occurrences of each element.

Does this mean that, the Max-3-DM with the bound 2 on the number of occurrences of each element in triples, is NP-hard?

I have found a polynomial reduction from the Max-3-DM with bound 2 to my problem, can I say that my problem is NP-hard?


Solution

  • If it is indeed NP-hard to approximate MAX-3DM with exactly two instances of each element within 95/94, then it's NP-hard to solve MAX-3DM with exactly two instances of each element. Specifically, if you could solve the problem exactly, then you could end up with an approximation better than 95/94 of the optimal solution (namely, you'd have something that was exactly accurate).

    Generally speaking, if it's NP-hard to approximate a problem to within a factor of 1+ε, it's NP-hard to solve it exactly because an exact solution is essentially a 1-approximation of the true answer.