1. Optimisation and Approximation

Optimisation vs. Approximation

A decision problem decides whether a solution exists or not. A optimisation problem tries to identify the best and most optimal solution.

For problems such as SAT, Halting, Hamiltonian Cycles, and Isomorphism it makes little sense to find the “most optimal solution”. However, problems such as Clique, Vertex Cover and the TSP (this week) are optimisation problems.

Optimisation Problems

Formal definition of optimisation problems

When looking at these problems, we can formalise them as such:

• The solution space, $S=\{\text{set of all possible solutions}\}$
• A cost function, $h:S\to \mathbb{Q}$ where $h(\text{solution})=\text{value of solution}$
  • We define a global maximum, $h(s_{\text{global}})\ge h(s)\text{ for all }s\in S$
  • Likewise a local maximum, $h(s_{\text{local}})\ge h(s)\text{ for all ’neighbouring’ }s\in S$

Link to original

Travelling Salesman Problem

General Travelling Salesman Problem

Given an input $G=(V,d)$ which is a complete weighted graph, where $d:V\times V\to \mathbb{Q}$ is a distance function. The output is the shortest Hamiltonian cycle visiting all vertices. Formalising this problem, we find:

$$\begin{array}{rl}S& =\{\text{all possible routes }H\}\\ h(H)& =\text{length of}(H)=\sum _{(x,y)\in H}d(x,y)\end{array}$$Link to original

We can also define this as a decision problem by adding an additional input $D\in \mathbb{Q}$, and output true if and only if $G$ contains a Hamiltonian cycle $H$ such that the $\text{length of}(H)\le D$.

TODO: add algorithms

Approximation Ratio

Approximation ratio

The approximation ratio for a given approximation algorithm $M$ on input $w$ is the real value $R_M(w)\ge 1$ such that:

$$\begin{array}{rl}{R}_M(w)& =max\left(\begin{array}{c}\frac{C_{\text{approx}}}{C_{\text{global}}},\frac{C_{\text{global}}}{C_{\text{approx}}}\end{array}\right)\\ & =\{\begin{array}{ll}\frac{C_{\text{approx}}}{C_{\text{global}}}& \text{if }{C}_{\text{global}}\le C_{\text{approx}}\\ \frac{C_{\text{global}}}{C_{\text{approx}}}& \text{if }{C}_{\text{global}}>C_{\text{approx}}\end{array}\end{array}$$

• Where $C_{\text{approx}}$ is the cost of the approximate solution.
• Where $C_{\text{global}}$ is the cost of the optimal solution.

Link to original

$R$-approximable problems

R-approximable problem

A language or problem $L$ is said to be $R$-approximable if there is some polynomial-time approximation algorithm $M$ such that $R_M(w)\le R$ for all $w\in {\Sigma }^{\ast }$.

$$C_{\text{approx}}\le R\times C_{\text{global}}$$Link to original

Unapproximable Problem

A language or problem $L$ is said to be unapproximable if $L$ is not R-approximable for any fixed value $R>0$. Or otherwise, any poly-time approximation algorithm $M$ must give arbitrarily bad solutions for some inputs.

Link to original