24
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What is the title of the book you mention? $\endgroup$ – Karolina Sołtys Oct 23 '10 at 20:44
  • 2
    $\begingroup$ I am not sure that is right. See page 2 of the notes linked in the question, specifically theorems 3 and 4 and the open problem stated just below theorem 4. The particular book I was referring to is Approximation Algorithms by Vijay Vazirani, which is excellent. $\endgroup$ – Raphael Oct 23 '10 at 21:20
  • $\begingroup$ Frieze and Kannan (research.microsoft.com/en-us/um/people/kannan/Papers/…) gave a randomized constant-time algorithm with additive error epsilon n^k for any max constraint satisfaction problem with arity k constraints. $\endgroup$ – Warren Schudy Oct 24 '10 at 19:17
  • $\begingroup$ I think bin packing being approximable to within OPT + 1 is entirely consistent with current knowledge. In fact the configuration LP is conjectured to have additive integrality gap 1 (I find the conjecture a bit wild, but there are no known counterexamples). $\endgroup$ – Sasho Nikolov Jun 26 '13 at 16:55
23
$\begingroup$

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-3SATs
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 n1−ε. 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

$\endgroup$
  • 3
    $\begingroup$ As another example, I think it'd be fairly natural to formulate the max-cut problem so that we maximise the fraction of edges in the cut. Again, we have both positive and negative results for additive approximation. $\endgroup$ – Jukka Suomela Oct 23 '10 at 22:44
  • 1
    $\begingroup$ @Jukka, Could you please provide a reference for this formulation of Max-cut? $\endgroup$ – Mohammad Al-Turkistany Oct 23 '10 at 22:51
  • 1
    $\begingroup$ Thanks very much. It seems that this is an area in need of at least a survey. The complexity zoo doesn't even mention additive error approximation classes as far as I can see (although it is so big I may have missed something). $\endgroup$ – Raphael Oct 24 '10 at 7:44
  • $\begingroup$ @Raphael: I would find a survey (or a pointer to one) rather useful. As far as I can tell, approximation algorithm classes were last surveyed about ten years ago, and I found the presentation far from clear. $\endgroup$ – András Salamon Oct 24 '10 at 14:13
6
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ Thanks. I notice that ABS is not listed in the complexity zoo qwiki.stanford.edu/index.php/Complexity_Zoo:A . Do you have a reference for it? $\endgroup$ – Raphael Oct 24 '10 at 6:51
  • $\begingroup$ Check this reference, citeseerx.ist.psu.edu/viewdoc/… $\endgroup$ – Mohammad Al-Turkistany Oct 24 '10 at 7:10
  • $\begingroup$ Am I right in thinking that the name ABS for the complexity class is one you just coined or is there a reference for it? The link you posted doesn't seem to mention it. $\endgroup$ – Raphael Oct 24 '10 at 19:17
  • $\begingroup$ @Raphael, No, I did not coin the name ABS, I read it somewhere long time ago. $\endgroup$ – Mohammad Al-Turkistany Oct 24 '10 at 19:51
6
$\begingroup$

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.

$\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.