If the weights of the weighted 3-DIMENSIONAL-MATCHING problem are restricted to let's say, 1 and 2, is there a possibility to reduce this case to the unweighted 3-DIMENSIONAL-MATCHING problem? (Because for the unweighted version, there is a (1.5+$\epsilon$)-approximation1 algorithm, for the weighted version, there is only a 2-approx2,3 algorithm)


  1. unweighted ($1.5+\epsilon$-approx)

  2. weighted ($2+\epsilon$-approx)

  3. weighted ($2$-approx) by CHAN, Yuk Hei, 2009

  • $\begingroup$ Good links (specially 2009 one), thanks. $\endgroup$ – user742 May 12 '12 at 15:03
  • $\begingroup$ So you need reductions that maintain approximation errors? $\endgroup$ – Raphael May 14 '12 at 15:38
  • $\begingroup$ Well, I can't even think of a reduction that doesn't. Of course, a reduction that maintains approximation would be great. $\endgroup$ – user1464 May 14 '12 at 19:24
  • $\begingroup$ @user1464: Well, some NP-complete problems admit FPTAS while others don't, so normal polynomial reduction destroys approximation bounds in general. $\endgroup$ – Raphael May 18 '12 at 0:42
  • $\begingroup$ Also see Section 4 of Three Dimensional Axial Assignment Problems with Decomposable Cost Coefficients, Discrete Applied Mathematics 65, 1996, 123-139 $\endgroup$ – sai Jul 6 '16 at 5:24

Your Answer

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

Browse other questions tagged or ask your own question.