Hardness of approximation - additive error

Question

There is a rich literature and at least one very good book setting out the known hardness of approximation results for NP-hard problems in the context of multiplicative error (e.g. 2-approximation for vertex cover is optimal assuming UGC). This also includes well understood approximation complexity classes such as APX, PTAS and so on.

What is known when additive error is to be considered? A literature search shows a few upper bound type results, most notably for bin packing (see for example http://www.cs.princeton.edu/courses/archive/spr03/cs594/dpw/lecture2.ps), but is there a more comprehensive complexity class classification or is there a reason why it is not so interesting or relevant?

As a further comment, for bin packing, for example, there is as far as I know no theoretical reason why a poly time algorithm which is always within an additive distance from optimal of 1 couldn't be found (although I stand to be corrected). Would such an algorithm collapse any complexity classes or have any other significant theoretical knock-on effect?

EDIT: The key phrase I didn't use is "asymptotic approximation class" (thanks Oleksandr). It seems that there is some work in this area but it hasn't got to the same stage of maturity yet as the theory of classic approximation classes.

Answer 1

The question is somewhat open-ended, so I do not think that it can be answered completely. This is a partial answer.

An easy observation is that many problems are uninteresting when we consider additive approximation. For example, traditionally the objective function of the Max-3SAT problem is the number of satisfied clauses. In this formulation, approximating Max-3SAT within an O(1) additive error is equivalent to solving Max-3SAT exactly, simply because the objective function can be scaled by copying the input formula many times. Multiplicative approximation is much more essential for the problems of this kind.

[Edit: In earlier revision, I had used Independent Set as an example in the previous paragraph, but I changed it to Max-3SAT because Independent Set is not a good example to illustrate the difference between multiplicative approximation and additive approximation; approximating Independent Set even within an O(1) multiplicative factor is also NP-hard. In fact, a much stronger inapproximability for Independent Set is shown by Håstad [Has99].]

But, as you said, additive approximation is interesting for the problems like bin packing, where we cannot scale the objective function. Moreover, we can often reformulate a problem so that additive approximation becomes interesting.

For example, if the objective function of Max-3SAT is redefined as the ratio of the number of satisfied clauses to the total number of clauses (as is sometimes done), additive approximation becomes interesting. In this setting, additive approximation is not harder than multiplicative approximation in the sense that approximability within a multiplicative factor 1−ε (0<ε<1) implies approximability within an additive error ε, because the optimal value is always at most 1.

An interesting fact (which seems to be unfortunately often overlooked) is that many inapproximability results prove the NP-completeness of certain gap problems which does not follow from the mere NP-hardness of multiplicative approximation (see also Petrank [Pet94] and Goldreich [Gol05, Section 3]). Continuing the example of Max-3SAT, it is a well-known result by Håstad [Has01] that it is NP-hard to approximate Max-3SAT within a constant multiplicative factor better than 7/8. This result alone does not seem to imply that it is NP-hard to approximate the ratio version of Max-3SAT within a constant additive error beyond some threshold. However, what Håstad [Has01] proves is stronger than the mere multiplicative inapproximability: he proves that the following promise problem is NP-complete for every constant 7/8<s<1:

Gap-3SAT_s
Instance: A CNF formula φ where each clause involves exactly three distinct variables.
Yes-promise: φ is satisfiable.
No-promise: No truth assignment satisfies more than s fraction of the clauses of φ.

From this, we can conclude that it is NP-hard to approximate the ratio version of Max-3SAT within an additive error better than 1/8. On the other hand, the usual, simple random assignment gives approximation within an additive error 1/8. Therefore, the result by Håstad [Has01] does not only give the optimal multiplicative inapproximability for this problem but also the optimal additive inapproximability. I guess that there are many additive inapproximability results like this which do not appear explicitly in the literature.

References

[Gol05] Oded Goldreich. On promise problems (a survey in memory of Shimon Even [1935-2004]). Electronic Colloquium on Computational Complexity, Report TR05-018, Feb. 2005. http://eccc.hpi-web.de/report/2005/018/

[Has99] Johan Håstad. Clique is hard to approximate within n^1−ε. Acta Mathematica, 182(1):105–142, March 1999. http://www.springerlink.com/content/m68h3576646ll648/

[Has01] Johan Håstad. Some optimal inapproximability results. Journal of the ACM, 48(4):798–859, July 2001. http://doi.acm.org/10.1145/502090.502098

[Pet94] Erez Petrank. The hardness of approximation: Gap location. Computational Complexity, 4(2):133–157, April 1994. http://dx.doi.org/10.1007/BF01202286

Answer 2

This is a partial answer

$ABS$ is the class of NP-optimization problems solvable in polynomial time to within an absolute additive error from the optimal solution. The following two problems are in $ABS$.

-A famous problem that has additive error approximation: 3-coloring of planar graphs is $NP$-complete while every planar graph is 4-colorable in polynomial time (by the four color theorem).

-Every cubic graphic is edge 4-colorable in polynomial time but edge 3-coloring is NP-hard.

Maximum independent set problem is not in $ABS$ unless $P=NP$

Answer 3

There is a recent work on asymptotic approximation classes and their comparison with classical counterparts.

Erik Jan van Leeuwen and Jan van Leeuwen. Structure of Polynomial-Time Approximation. Technical Report UU-CS-2009-034. December 2009.