As you said, there is no decision to make, so new complexity classes and new types of reductions are needed to arrive at a suitable definition of NP-hardness for optimization-problems.
One way of doing this is to have two new classes NPO and PO that contain optimizations problems and they mimic of course the classes NP and P for decision problems. New reductions are needed as well. Then we can recreate a version of NP-hardness for optimization problems along the lines that was successful for decision problems. But first we have to agree what an optimization-problem is.
Definition: Let $O=(X,L,f,opt)$ be an optimization-problem. $X$ is the set of inputs or instances suitable encoded as strings. $L$ is a function that maps each instance $x\in X$ onto a set of strings, the feasible solutions of instance $x$. It is a set because there are many solutions to an optimization-problem. Thus we haven an objective function $f$ that tells us for every pair $(x, y)$ $y\in L(x)$ of instance and solution its cost or value. $opt$ tells us whether we are maximizing or minimizing.
This allows us to define what an optimal solution is: Let $y_{opt}\in L(x)$ be the optimal solution of an instance $x\in X$ of an optimization-problem $O=(X,L,f,opt)$ with $$f(x,y_{opt})=opt\{f(x,y')\mid y'\in L(x)\}.$$ The optimal solution is often denoted by $y^*$.
Now we can define the class NPO: Let $NPO$ be the set of all optimization-problems $O=(X,L,f,opt)$ with:
- $X\in P$
- There is a polynomial $p$ with $|y|\le p(|x|)$ for all instances $x\in X$ and all feasible solutions $y\in L(x)$. Furthermore there is an deterministic algorithm that decides in polynomial time whether $y\in L(x)$.
- $f$ can be evaluated in polynomial time.
The intuition behind it is:
- We can verify efficiently if $x$ is actually a valid instance of our optimization problem.
- The size of the feasible solutions is bounded polynomially in the size of the inputs, And we can verify efficiently if $y\in L(x)$ is a fesible solution of the instance $x$.
- The value of a solution $y\in L(x)$ can be determined efficiently.
This mirrors how $NP$ is defined, now for PO: Let $PO$ be the set of all problems from $NPO$ that can be solved by an deterministic algorithm in polynomial time.
Now we are able to define what we want to call an approximation-algorithm: An approximation-algorithm of an optimization-problem $O=(X,L,f,opt)$ is an algorithm that computes a feasible solution $y\in L(x)$ for an instance $x\in X$.
Note: That we don’t ask for an optimal solution we only what to have a feasible one.
Now we have two types of errors: The absolute error of a feasible solution $y\in L(x)$ of an instance $x\in X$ of the optimization-problem $O=(X,L,f,opt)$ is $|f(x,y)-f(x,y^*)|$.
We call the absolute error of an approximation-algorithm $A$ for the optimization-problem $O$ bounded by $k$ if the algorithm $A$ computes for every instance $x\in X$ a feasible solution with an absolute error bounded by $k$.
Example: According to the Theorem of Vizing the chromatic index of a graph (the number of colours in the edge coloring with the fewest number of colors used) is either $\Delta$ or $\Delta+1$, where $\Delta$ is the maximal node degree. From the proof of the theorem an approximation-algorithm can be devised that computes an edge coloring with $\Delta+1$ colours. Accordingly we have an approximation-algorithm for the $\mathsf{Minimum-EdgeColoring}$-Problem where the absolute error is bounded by $1$.
This example is an exception, small absolute errors are rare, thus we define the relative error $\epsilon_A(x)$ of the approximation-algorithm $A$ on instance $x$ of the optimization-problem $O=(X,L,f,opt)$ with $f(x,y)>0$ for all $x\in X$ and $y\in L(x)$ to be
$$\epsilon_A(x):=\begin{cases}0&f(x,A(x))=f(x,y^*)\\\frac{|f(x,A(x))-f(x,y^*)|}{\max\{f(x,A(x)),f(x,y^*)\}}&f(x,A(x))\ne f(x,y^*)\end{cases}$$
where $A(x)=y\in L(x)$ is the feasible solution computed by the approximation-algorithm $A$.
We can now define approximation-algorithm $A$ for the optimization-problem $O=(X,L,f,opt)$ to be a $\delta$-approximation-algorithm for $O$ if the relative error $\epsilon_A(x)$ is bounded by $\delta\ge 0$ for every instance $x\in X$, thus
$$\epsilon_A(x)\le \delta\qquad \forall x\in X.$$
The choice of $\max\{f(x,A(x)),f(x,y^*)\}$ in the denominator of the definition of the relative error was selected to make the definition symmetric for maximizing and minimizing. The value of the relative error $\epsilon_A(x)\in[0,1]$. In case of a maximizing problem the value of the solution is never less than $(1-\epsilon_A(x))\cdot f(x,y^*)$ and never larger than $1/(1-\epsilon_A(x))\cdot f(x,y^*)$ for a minimizing problem.
Now we can call an optimization-problem $\delta$-approximable if there is a $\delta$-approximation-algorithm $A$ for $O$ that runs in polynomial time.
We do not want to look at the error for every instance $x$, we look only at the worst-case. Thus we define $\epsilon_A(n)$, the maximal relativ error of the approximation-algorithm $A$ for the optimization-problem $O$ to be
$$\epsilon_A(n)=\sup\{\epsilon_A(x)\mid |x|\le n\}.$$
Where $|x|$ should be the size of the instance.
Example: A maximal matching in a graph can be transformed in to a minimal node cover $C$ by adding all incident nodes from the matching to the vertex cover. Thus $1/2\cdot |C|$ edges are covered. As each vertex cover including the optimal one must have one of the nodes of each covered edge, otherwise it could be improved, we have $1/2\cdot |C|\cdot f(x,y^*)$. It follows that $$\frac{|C|-f(x,y^*)}{|C|}\le\frac{1}{2}$$
Thus the greedy algorithm for a maximal matching is a $1/2$-approximatio-algorithm for $\mathsf{Minimal-VertexCover}$. Hence $\mathsf{Minimal-VertexCover}$ is $1/2$-approximable.
Unfortunately the relative error is not always the best notion of quality for an approximation as the following example demonstrates:
Example: A simple greedy-algorithm can approximate $\mathsf{Minimum-SetCover}$. An analysis shows that $$\frac{|C|}{|C^*|}\le H_n\le 1+\ln(n)$$ and thus $\mathsf{Minimum-SetCover}$ would be $\frac{\ln(n)}{1+\ln(n)}$-approximable.
If the relative error is close to $1$ the following definition is advantageous.
Let $O=(X,L,f,opt)$ be an optimization-problem with $f(x, y)>0$ for all $x\in X$ and $y\in L(x)$ and $A$ an approximation-algorithm for $O$. The approximation-ratio $r_A(x)$ of feasible solution $A(x)=y\in L(x)$ of the instance $x\in X$ is
$$r_A(x)=\begin{cases}1&f(x,A(x))=f(x,y^*)\\\max\left\{
\frac{f(x,A(x))}{f(x, y^*)},\frac{f(x, y^*)}{f(x, A(x))}\right\}&f(x,A(x))\ne f(x,y^*)\end{cases}$$
As before we call an approximation-algorithm $A$ an $r$-approximation-algorithm for the optimization-problem $O$ if the approximation-ratio $r_A(x)$ is bounded by $r\ge1$ for every input $x\in X$.
$$r_A(x)\le r$$
And yet again if we have an $r$-approximation-algorithm $A$ for the optimization-problem $O$ then $O$ is called $r$-approximable. Again we only care about to the worst-case and define the maximal approximation-ratio $r_A(n)$ to be
$$r_A(n)=\sup\{r_A(x)\mid |x|\le n\}.$$
Accordingly the approximation-ratio is larger than $1$ for suboptimal solutions. Thus better solutions have smaller ratios. For $\mathsf{Minimum-SetCover}$ we can now write that it is $(1+\ln(n))$-approximable. And in case of $\mathsf{Minimum-VertexCover}$ we know from the previous example that it is $2$-approximable. Between relative error and approximation-ratio we have simple relations:
$$r_A(x)=\frac{1}{1-\epsilon_A(x)}\qquad \epsilon_A(x)=1-\frac{1}{r_A(x)}.$$
For small deviations from the optimum $\epsilon<1/2$ and $r<2$ the relative error is advantageous over the approximation-ratio, that shows its strengths for large deviations $\epsilon\ge 1/2$ and $r\ge 2$.
The two versions of $\alpha$-approximable don’t overlap as one version has always $\alpha\le 1$ and the other $\alpha\ge 1$. The case $\alpha=1$ is not problematic as this is only reached by algorithms that produce an exact solution and consequentially need not be treated as approximation-algorithms.
Another class appears often APX. It is define as the set of all optimization-problems $O$ from $NPO$ that haven an $r$-approximation-algorithm with $r\ge1$ that runs in polynomial time.
We are almost through. We would like to copy the successful ideas of reductions and completness from complexity theory. The observation is that many NP-hard decision variants of optimization-problems are reducible to each other while their optimization variants have different properties regarding their approximability. This is due to the polynomialtime-Karp-reduction used in NP-completness reductions, which does not preserve the objective function. And even if the objective functions is preserved the polynomialtime-Karp-reduction may change the quality of the solution.
What we need is a stronger version of the reduction, which not only maps instances from optimization-problem $O_1$ to instances of $O_2$, but also good solutions from $O_2$ back to good solutions from $O_1$.
Hence we define the approximation-preserving-reduction for two optimization-problems $O_1=(X_1,L_1,f_1,opt_1)$ and $O_2=(X_2,L_2,f_2,opt_2)$ from $NPO$. We call $O_1$ $AP$-reducible to $O_2$, written as $O_1\le_{AP} O_2$, if there are two functions $g$ and $h$ and a constant $c$ with:
- $g(x_1, r)\in X_2$ for all $x_1\in X_1$ and rational $r>1$
- $L_2(g(x, r_1))\ne\emptyset$ if $L_1(x_1)\ne\emptyset$ for all $x_1\in X_1$ and rational $r>1$
- $h(x_1, y_2, r)\in L_1(x_1)$ for all $x_1\in X_1$ and rational $r>1$ and for all $y_2\in L_2(g(x_1,r))$
- For fixed $r$ both functions $g$ and $h$ can be computed by two algorithms in polynomial time in the length of their inputs.
- We have $$f_2(g(x_1,r),y_2)\le r \Rightarrow f_1(x_1,h(x_1,y_2,r))\le 1+c\cdot(r-1) $$ for all $x_1\in X_1$ and rational $r>1$ and for all $y_2\in L_2(g(x_1,r))$
In this definition $g$ and $h$ depend on the quality of the solution $r$. Thus for different qualities the functions can differ. This generality is not always needed and we just work with $g(x_1)$ and $h(x_1, y_2)$.
Now that we have a notion of a reduction for optimization-problems we finally can transfer many things we know from complexity theory. For example if we know that $O_2\in APX$ and we show that $O_1\le_{AP} O_2$ it follows that $O_1\in APX$ too.
Finally we can define what we mean by $\mathcal{C}$-hard and $\mathcal{C}$-complete for optimization-problems:
Let $O$ be an optimization-problem from $NPO$ and $\mathcal{C}$ a class of optimization-problems from $NPO$ then $O$ is called $\mathcal{C}$-hard with respect to $\le_{AP}$ if for all $O'\in\mathcal{C}$ $O'\le_{AP} O$ holds.
Thus once more we have a notion of a hardest problem in the class. Not surprising a $\mathcal{C}$-hard problem is called $\mathcal{C}$-complete with respect to $\le_{AP}$ if it is an element of $\mathcal{C}$.
Thus we can now talk about $NPO$-completness and $APX$-completness etc. And of course we are now asked to exhibit a first $NPO$-complete problem that takes over the role of $\mathsf{SAT}$. It comes almost naturally, that $\mathsf{Weighted-Satisfiability}$ can be shown to be $NPO$-complete. With the help of the PCP-Theorem one can even show that $\mathsf{Maximum-3SAT}$ is $APX$-complete.
