Exact Optimisation via Integrality (FPTAS)

Definition

Exact Optimisation via Integrality (FPTAS)

Let $\Pi$ be an NP-optimisation problem with integer objective function

$$f_{\Pi }:S_{\Pi }\to \mathbb{Z},$$

s.t. on every instance $I$ the optimal value of $I$ satisfies

$$\mathrm{OPT}(I)<p(||I|{|}_{\mathrm{una}})$$

for some polynomial $p$, where $||I|{|}_{\mathrm{una}}$ denotes the length of the unary encoding of $I$.

If $\Pi$ admits an FPTAS, then it also admits a pseudo-polynomial time algorithm .

Proof for Maximisation Problems

Proof for Maximisation Problems

Let $\mathcal{A}$ be an FPTAS for $\Pi$, and assume

$$\mathrm{OPT}(I)<p(||I|{|}_{\mathrm{una}}),$$

where $||I|{|}_{\mathrm{una}}$ is the length of the unary encoding of $I$, for some polynomial $p$. Also assume that the objective values are integers.

Choose $\epsilon$ so the approximation error is $<1$.

Set

$$\epsilon :=\frac{1}{p(||I|{|}_{\mathrm{una}})}<1.$$

Given that $\mathcal{A}$ is an FPTAS,

$$f_{\Pi }(S_A)\ge (1-\epsilon )\cdot \mathrm{OPT}(\mathrm{I})=\mathrm{OPT}(I)-\epsilon \cdot \mathrm{OPT}(I).$$

Given the assumption $\mathrm{OPT}(I)<p(||I|{|}_{\mathrm{una}})$, we get

$$\begin{array}{rl}\mathrm{OPT}(I)<p(||I|{|}_{\mathrm{una}})⟹f_{\Pi }(S_A)& >\mathrm{OPT}(I)-\epsilon p(||I|{|}_{\mathrm{una}})\\ & =\mathrm{OPT}(I)-1.\end{array}$$

Integrality makes the solution exact.

We always have that

$$f_{\Pi }(S_A)\le \mathrm{OPT}(I).$$

Together with the above, i.e.,

$$f_{\Pi }(S_A)>\mathrm{OPT}(\mathrm{I})-1,$$

we get the inequality chain

$$\mathrm{OPT}(I)-1<f_{\Pi }(S_A)\le \mathrm{OPT}(I).$$

Both values are integers, forcing

$$f_{\Pi }(S_A)=\mathrm{OPT}(I).$$

Thus $\mathcal{A}$ returns an optimal solution for this choice of $\epsilon$.

Show that $\mathcal{A}$ is pseudo-polynomial.

An FPTAS $\mathcal{A}$ runs in

$$T(I,\epsilon )={\left(\frac{||I|{|}_{\mathrm{bin}}}{\epsilon }\right)}^{O(1)}.$$

Substitute

$$T\left(I,\frac{1}{p(||I|{|}_{\mathrm{una}})}\right)={\left(||I|{|}_{\mathrm{bin}}\cdot p(||I|{|}_{\mathrm{una}})\right)}^{O(1)}.$$

Since binary encoding is compact, we know that

$$||I|{|}_{\mathrm{bin}}\le ||I|{|}_{\mathrm{una}},$$

i.e., this is polynomial in $||I|{|}_{\mathrm{una}}$. Therefore, $\mathcal{A}$ is pseudo-polynomial.