Optimization problems and approximation ratios

A finite-instance optimization problem consists of the following data.

• A problem domain of explicitly encoded finite instances, each with a finite encoding length $\mathrm{\mid }x\mathrm{\mid }$.
• A polynomial solution-length bound: a polynomial $p$ such that every feasible solution $y$ of an instance $x$ satisfies $\mathrm{\mid }y\mathrm{\mid }\le p(\mathrm{\mid }x\mathrm{\mid })$.
• A feasible-solution relation $R(x,y)$, recognizable in deterministic time polynomial in $\mathrm{\mid }x\mathrm{\mid }+\mathrm{\mid }y\mathrm{\mid }$.
• A nonnegative rational objective $\mathrm{val}(x,y)\in \mathbb{Q}$ with $\mathrm{val}(x,y)\ge 0$, computable in deterministic time polynomial in $\mathrm{\mid }x\mathrm{\mid }+\mathrm{\mid }y\mathrm{\mid }$ for every feasible $y$.
• A direction, either minimization or maximization.

Every instance of the stated domain is assumed to have at least one feasible solution. For an instance $x$, the feasible solutions lie in the finite set of strings of length at most $p(\mathrm{\mid }x\mathrm{\mid })$; hence the set of values $\{\mathrm{val}(x,y):R(x,y)\}$ is a finite nonempty set of nonnegative rationals, and its minimum or maximum, as selected by the direction,

$\mathrm{OPT}(x):=\min \text{ or }\max \{\mathrm{val}(x,y):R(x,y)\},$

is attained. The order of the quantifiers is fixed: $\mathrm{OPT}(x)$ is defined for every domain instance, independently of any algorithm.

Let $\rho$ be rational. A polynomial-time algorithm is a $\rho$-approximation for the problem when it runs in deterministic time polynomial in $\mathrm{\mid }x\mathrm{\mid }$ and, on every domain instance $x$, outputs a feasible solution $y$ whose value satisfies

$\mathrm{val}(x,y)\le \rho \mathrm{OPT}(x)(\rho \ge 1,\text{ minimization}),$

$\mathrm{val}(x,y)\ge \rho \mathrm{OPT}(x)(0<\rho \le 1,\text{ maximization})\mathrm{.}$

These are inequalities between values, not quotients: they include the case $\mathrm{OPT}(x)=0$, where the minimization inequality asks for a feasible solution of value $0$ and the maximization inequality is automatic, and neither guarantee is formed by dividing by $\mathrm{OPT}(x)$. Suitable examples fixed later on this page are minimum vertex cover, weighted set cover, max-cut, metric TSP, max-3SAT and maximum independent set, always with explicitly encoded rational instance data.

For the max-cut problem used below, the instances are the finite simple graphs, a feasible solution is a bipartition of the vertex set, the objective is the number of edges whose endpoints lie in different parts, and ${\mathrm{OPT}}_{\mathrm{M}\mathrm{a}\mathrm{x}\mathrm{C}\mathrm{u}\mathrm{t}}$ denotes the attained maximum over the finitely many bipartitions. For a randomized algorithm, the $1\mathrm{/}2$-guarantee is read in the value form $\mathbb{E}[\text{value}]\ge \frac{1}{2}{\mathrm{OPT}}_{\mathrm{M}\mathrm{a}\mathrm{x}\mathrm{C}\mathrm{u}\mathrm{t}}$ of the maximization inequality above.