4
$\begingroup$

I know this question is trivial. But I am looking for a concise formal definition of $\alpha$-approximation.

Is it correct to say that "An algorithm is an $\alpha$-approximation to problem $X$, if for any instance of problem $X$ the solution returned by this algorithm is within a factor $\alpha$ of the optimal solution"?

Any correction on the above definition is welcomed.

$\endgroup$
  • 1
    $\begingroup$ Well, have you looked into a textbook, or any other resource? $\endgroup$ – Raphael Jul 29 '17 at 6:26
  • 1
    $\begingroup$ It looks correct to me. $\endgroup$ – md5 Jul 29 '17 at 19:16
  • $\begingroup$ @Raphael I searched a lot on the Internet but I couldn't find a standard definition. I looked at ALgortihm design book by Jon Kleinberg. There are something there, but not so formal $\endgroup$ – m0_as Jul 29 '17 at 19:27
5
$\begingroup$

There are actually two main types of approximation algorithms: those that return an approximate solution, and those that return the approximate value. In order to explain the difference, let me define the problem more formally. Below everything is stated for minimization problems. It is a simple exercise to generalize everything for maximization problems.

Let me stress that the definitions below are not standard; in fact, there is no standard agreed-upon definition. However, it can be taken as a formal definition without too many complaints from the community, if you find this kind of definition enlightening.

Definition: A minimization problem consists of a tuple $\mathcal{O},\mathcal{S},v$ such that:

  • $\mathcal{O}$ is the set of instances.
  • $\mathcal{S}$ is the set of solutions.
  • $v$ is a function from $\mathcal{O} \times \mathcal{S}$ to $\mathbb{R}_+ \cup \{\infty\}$ (the non-negative reals together with positive infinity) such that for every $o \in \mathcal{O}$ there exists $s \in \mathcal{S}$ such that $v(o,s) < \infty$.

We define $v^*(o) = \inf_{s \in \mathcal{S}} v(o,s)$.

The function $v$ is the value of the given solution for a given instance. The optimal value for the instance is $v^*(o)$. If $v(o,s) = \infty$ then we say that the solution is infeasible for the instance.

(Alternatively, we could have a function $f\colon \mathcal{O} \to 2^{\mathcal{S}} \setminus \{\emptyset\}$ giving the (non-empty) set of feasible solutions, and then $v$ is a partial function $\mathcal{O} \times \mathcal{S} \to \mathbb{R}_+$ such that $v(o,s)$ is defined iff $s \in f(o)$.)

Definition: An $\alpha$-approximation algorithm is an algorithm $A\colon \mathcal{O} \to \mathcal{S}$ that satisfies the following property:

For all $o \in \mathcal{O}$, $v(o,A(o)) \leq \alpha v^*(o)$.

If $\alpha = 1$, then the algorithm finds an optimal solution.

We are usually interested in polynomial time approximation algorithms. In this case we have to fix an encoding for $\mathcal{O}$ and $\mathcal{S}$, that is, we should treat $\mathcal{O},\mathcal{S}$ not as abstract sets but rather as sets of strings.

Definition: A weak $\alpha$-approximation algorithm (non-standard terminology) is an algorithm $B\colon \mathcal{O} \to \mathbb{R}_+$ such that:

For all $o \in \mathcal{O}$, $v^*(o) \leq B(o) \leq \alpha v^*(o)$.

Once again, we are usually interested in polynomial time algorithms. Given an $\alpha$-approximation algorithm $A$, we can construct a weak $\alpha$-approximation algorithm $B$ using $B(o) = v(o,A(o))$ (this works assuming $v$ is computable). In many specific case we can also go in the other direction.

In some cases (especially hardness of approximation proofs), when the phrase "$\alpha$-approximation algorithm" has the weaker meaning given in the latter definition.

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