# matching – Hardness of multiplicative vs. additive approximation

Chlebik and Chlebikova prove that the problem “maximum 3-dimensional matching” is NP-hard to approximate within a multiplicative factor of $$95/94$$.
This means that, unless $$P=NP$$, there is no polynomial-time algorithm that finds a 3-dimensional matching with at least $$(94/95)cdot OPT$$ edges, where $$OPT$$ is the number of edges in a maximum matching.

Suppose we would like an additive approximation algorithm, that finds a 3-dimensional matching with at least $$OPT-1$$ edges. Is such algorithm theoretically possible (if $$Pneq NP$$)?