Polynomial-time Approximation Schemes (PTAS)

During the 6th semester of my BSc studies I have chosen to attend a seminar on Theoretical Computer Science. My task was to present the topic “polynomial-time approximation schemes” to the others. In this article I am sharing the work. Also available are the slides.

Author: Timo I. Denk
Baden-Württemberg Cooperative State University Karlsruhe
Supervisor: Dr. Martin Holzer
Date of publication: April 12, 2019

1 Introduction

The complexity class of nondeterministic polynomial time algorithms ($\mathit{NP}$) contains problems for which there is no known deterministic polynomial time ($\mathit{P}$) algorithm that is guaranteed to find the exact solution. These problems are, however, of practical relevance, which is why effort was put into developing algorithms capable of finding approximate solutions. While simple heuristics might work well for some specific instances of a problem, they often cannot guarantee how much the quality of the result will diverge from the quality of an optimal solution.

Polynomial-time approximation schemes (PTAS) are a family of algorithms in $\mathit{P}$ that finds approximate solutions to instances of NP-problems, while making an explicit guarantee about the relative quality of the approximations when compared to the optimal solutions.

We give definitions in Section 2, most importantly the ones for PTAS and FPTAS. The latter is an even more stringent version of PTAS. Section 3 contains example algorithms. We outline and prove an FPTAS for the sweet-tempered, though $\mathit{NP}$-complete Knapsack problem (Section 3.1) and contrast it with the (also $\mathit{NP}$-complete) Traveling Salesman problem (Section 3.2) for which no PTAS exists.

This work was carried out as part of Computer Science BSc studies at Corporative State University Karlsruhe, in a seminar on Theoretical Computer Science. The corresponding slides can be found at https://timodenk.com/talks/ptas.

2 Definitions

Let $\Pi$ denote an optimization problem, where the set of possible instances of the problem is $D_\Pi$, with $I\in D_\Pi$ being one of these instances. An instance has a size $\lvert I\rvert$, referred to as $n$. We assume that all numbers occurring in $I$ are encoded in binary. For each instance, there exists a nonempty set of possible solutions, each of which is associated with an objective function value $\in\mathbb{R}^+$ (e.g. the cost of a solution).

Let $\text{OPT}(I)$, $\text{OPT}$ for short, denote the optimal objective function value for an instance $I\in D_\Pi$ of problem $\Pi$. That is from all possible solutions, $\text{OPT}$ is the score of the solution with the lowest score. In case of maximization problems, $\text{OPT}$ is the highest score possible. For the following problems, computing $\text{OPT}$ is NP-hard.

2.1 Polynomial and Pseudo-polynomial Time Algorithms

Algorithms with runtime complexity $\mathcal{O}(n^\alpha)$ for some constant $\alpha\ge1$ are called polynomial time algorithms. A polynomial time approximation algorithm $\mathcal{A}$ for the problem $\Pi$ computes an approximate solution for a given problem instance $I$. Specifically, $\mathcal{A}(I)$ denotes the objective function value of the solution that $\mathcal{A}$ outputs for $I$.

Let $I_\text{u}$ denote the variant of instance $I$ where all contained numbers have a unary representation. $\lvert I_\text{u}\rvert$ is the unary size of instance $I$. A pseudo-polynomial algorithm $\mathcal{A}$ for problem $\Pi$ computes exact solutions for all instances while being polynomial in $\lvert I_\text{u}\rvert$ but not necessarily in $n$. Take for example an algorithm that determines whether a number, e.g. $9$, is a prime. The two representations are $I=(1001)_\text{b}$ (binary encoding of $9$) and $I_\text{u}=(111111111)_\text{u}$ ($9\times$ the symbol $1$). An algorithm with $\mathcal{O}(\lvert I_\text{u}\rvert)$ runtime takes linearly more time as the number grows, opposed to an $\mathcal{O}(\lvert I\rvert)$-algorithm which may only take logarithmically more time.

2.2 Polynomial-time Approximation Scheme

$\mathcal{A}_\epsilon$ is a polynomial-time approximation scheme (PTAS) for a minimization problem $\Pi$ (lower objective function values are better), if $$ \begin{equation}\label{eq:ptas}
\forall I\in D_\Pi
\left[
\frac{\mathcal{A}_\epsilon(I)}{\text{OPT}(I)}\le1+\epsilon
\right],\tag{1}
\end{equation} $$ where the parameter $\epsilon\in\mathbb{R}^+$ denotes the upper bound of the quality of the solutions of $\mathcal{A}_\epsilon$ relative to the optimal solution. Analogous, a PTAS for maximization problems satisfies $\forall I\in D_\Pi\left[\frac{\mathcal{A}_\epsilon(I)}{\text{OPT}(I)}\ge1-\epsilon\right]$.

Verbally described, the relative difference between the objective function value of the optimal solution and the approximated solution must not exceed $\epsilon$ for all possible instances $I\in D_\Pi$ of the problem $\Pi$.

Let $K\in\mathbb{R}^+$ be a constant. $\mathcal{A}$ is a PTAS with absolute performance guarantee for a minimization problem $\Pi$, if \begin{equation}
\forall I\in D_\Pi
[
\mathcal{A}(I)-
\text{OPT}(I)
\le K
],.\tag{2}
\end{equation}Verbally described, this means the solution found by the approximative algorithm $\mathcal{A}$ is at most $K$ worse than the optimal solution that can be found, in terms of the objective function value. This must hold true for all possible instances $I\in D_\Pi$ of the problem $\Pi$.

Absolute approximation schemes have little practical relevance as they are very rare. Thus, in the following, PTAS will refer to PTAS with relative (not absolute) performance guarantees.

2.3 Fully Polynomial-time Approximation Scheme

The time complexity of a PTAS is polynomial in $n$ but may grow exponentially or even faster with respect to $\epsilon$. Therefore, algorithms running in e.g. $\mathcal{O}(n^\frac{1}{\epsilon})$ or $\mathcal{O}(n^{\frac{1}{\epsilon}!})$ are still PTASs.

A fully polynomial-time approximation scheme (FPTAS) $\mathcal{A}_\epsilon$ is polynomial in both $n$ and $\frac{1}{\epsilon}$, i.e. the algorithm has a runtime complexity of $\mathcal{O}\left(\frac{n^\alpha}{\epsilon^\beta}\right)$ for constant $\alpha,\beta\ge1$.

Intuitively, this can be understood as a guarantee that an increase of the problem size $n$ or an increase of approximation quality $\frac{1}{\epsilon}$ does not affect the runtime more than polynomially.

Unless $\mathit{P}=\mathit{NP}$, it holds that $\mathit{FPTAS}\subsetneq\mathit{PTAS}$; see e.g. Jansen (1997). Here $\mathit{FPTAS}$ denotes the set of all problems for which an FPTAS exists and, accordingly, $\mathit{PTAS}$ is the set of all problems for which a PTAS exists.

3 Examples

This section explores some example problems and (F)PTAS solutions to them, alongside with evidence for the performance guarantees. Vazirani (2013) provides a comprehensive overview of approximation algorithms and, unless indicated otherwise, serves as the basis for the following content.

3.1 Knapsack Problem

The Knapsack problem admits an FPTAS. This section is based on course notes by de Berg (2017) and is structured as follows: We review the Knapsack problem definition and provide a pseudo-polynomial time algorithm for it. Subsequently, we present an FPTAS and prove its error bound.

Problem statement. A problem instance $I$ is made up of a maximum capacity $W\in\mathbb{Z}^+$ and a set of objects $X={x_1,\dots,x_n}$, each associated with a $\operatorname{weight}(x_i)\in\mathbb{Z}^+\le W$ and a $\operatorname{profit}(x_i)\in\mathbb{Z}^+$. We define $\operatorname{weight}(S)=\sum_{x\in S}\operatorname{weight}(x)$ and $\operatorname{profit}(S)=\sum_{x\in S}\operatorname{profit}(x)$, where $S\subseteq X$. The Knapsack problem’s goal is to find an $S$ that maximizes the objective function $\operatorname{profit}(S)$ under the constraint $\operatorname{weight}(S)\le W$.

A pseudo-polynomial solution for Knapsack exists. With $P=\operatorname{profit}(X)$ and $n=\lvert X\rvert$, a dynamic-programming (DP) algorithm will run in $\mathcal{O}(nP)$. However, $P$ can be arbitrarily large. We present the DP algorithm at this point, because it serves as a subroutine for the FPTAS (introduced later in this section) which runs polynomially in $n$ while being independent of $P$.

For $0\le i\le n$ and $0\le p\le P$ we define a matrix $\boldsymbol{A}\in\mathbb{Z}^{(n+1)\times(P+1)}$:
\begin{align}\label{eq:knapsacksetselection}
A_{i,p}:=\min\left\{\operatorname{weight}(S):S\subseteq{x_1,\dots,x_i}\land\operatorname{profit}(S)=p\right\},.\tag{3}
\end{align}An entry at $i,p$ in $\boldsymbol{A}$ is the minimum weight of a subset of all items until $x_i$, that has exactly the profit $p$. If there is no such subset, $A_{i,p}:=\infty$. The maximum profit is given by $\text{OPT}(I)=\max_{0\le p\le P}\left\{p:A_{n,p}\le W\right\}$. $\boldsymbol{A}$ can be computed recursively:
\begin{align}
A_{i,p}:=\begin{cases}
p\times\infty &\text{if }p=0\lor i=0\\
A_{i-1,p} &\text{else if }p<\operatorname{profit}(x_i)\\
\min\left(A_{i-1,p},A_{i-1,p-\operatorname{profit}(x_i)}+\operatorname{weight}(x_i)\right) & \text{otherwise},.
\end{cases}\tag{4}
\end{align}The recursive definition illustrates that each entry in $\boldsymbol{A}$ only depends on the previous rows/columns. Therefore, the matrix can be computed in a bottom-up manner and $\text{OPT}$ can be determined afterwards.

FPTAS. Based on the pseudo-polynomial solution, we construct an FPTAS whose error $\text{OPT}(I)-\mathcal{A}_\epsilon(I)$ is at most $\epsilon\times\text{OPT}$ (referred to as a $(1-\epsilon)$-approximation). The idea is to dispense with the $P$ factor in the runtime complexity $\mathcal{O}(nP)$ of the pseudo-polynomial solution by downscaling all profits by some $\sigma\in\mathbb{R}^+$ and subsequent rounding to the next largest integer:
\begin{equation}
\left\lceil\frac{\operatorname{profit}(x_i)}{\sigma}\right\rceil,.\tag{5}
\end{equation}Downscaling introduces some error since the algorithm may sometimes chose a subset over another subset erroneously (see Equation \ref{eq:knapsacksetselection}). Suppose we chose $\sigma=\frac{\epsilon}{n}\times\text{OPT}$. Every rounding introduces an error of at most $1$ per object and there are no more than $n$ objects in a subset. Therefore, with this scaling factor, the error in finding the subset with the minimum weight is off by at most $\epsilon\times\text{OPT}$. However, $\text{OPT}$ is unknown to us so we cannot scale the profits by it. Hence, we choose $\sigma=\frac{\epsilon}{n}\times\text{LB}$, where the lower bound $\text{LB}=\max_i\operatorname{profit}(x_i)$ is known to be $\le\text{OPT}$ because every item $x_i$ satisfies $\operatorname{weight}(x_i)\le W$. The new profits
\begin{equation}\label{eq:knapsacknewprofits}
\operatorname{profit}^*(x_i)=\left\lceil\frac{n}{\epsilon}\frac{\operatorname{profit}(x_i)}{\max_j\operatorname{profit}(x_j)}\right\rceil\tag{6}
\end{equation}are all known to be $\in\left\{1,\dots,\left\lceil\frac{n}{\epsilon}\right\rceil\right\}$.

The Knapsack-FPTAS takes the inputs and uses the new profits induced by $\operatorname{profit}^*$ as input to the DP algorithm. The resulting approximation runs in $\mathcal{O}\left(\frac{n^3}{\epsilon}\right)$ time, because the new $P^*$ is at most $n\times\left\lceil\frac{n}{\epsilon}\right\rceil$ and the pseudo-polynomial algorithm runs in $\mathcal{O}(nP^*)$. The Knapsack-FPTAS is therefore polynomial in both $n$ and $\frac{1}{\epsilon}$. The presented strategy can be transferred to other problems with DP solutions as well. Woeginger (2000) investigates under which conditions a DP solution guarantees the existence of an FPTAS.

Approximation ratio proof. To complete the Knapsack example we prove Equation \ref{eq:ptas} for $\Pi=\text{Knapsack}$, i.e.
$$ \begin{equation}
\mathcal{A}_\epsilon(I)\ge(1-\epsilon)\times\text{OPT}(I),\tag{7}
\end{equation} $$ where $\mathcal{A}_\epsilon(I)$ is the profit of the solution found by the FPTAS. Note that instead of $(1+\epsilon)$ we use $(1-\epsilon)$ because Knapsack, as formulated above, is a maximization (not a minimization) problem. $\text{OPT}$ is short for $\text{OPT}(I)$.

Let $S_\text{OPT}$ denote the optimal solution and $S^*$ the solution found by the FPTAS. $$ \begin{align*}
\text{OPT}=&\sum_{x_i\in S_\text{OPT}}\operatorname{profit}(x_i)\\
\le&\sum_{x_i\in S_\text{OPT}}\frac{\epsilon}{n}\times\text{LB}\times\operatorname{profit}^*(x_i)\\
\le&\frac{\epsilon}{n}\times\text{LB}\times\operatorname{profit}^*(S_\text{OPT})\\
\le&\frac{\epsilon}{n}\times\text{LB}\times\operatorname{profit}^*(S^*)
\end{align*} $$ The inequalities hold because the ceiling from Equation \ref{eq:knapsacknewprofits} only increases the profit values.

Furthermore, we know that $\operatorname{profit}^*(S^*)$ can be rewritten as $\sum_{x_i\in S^*}\left\lceil\frac{n}{\epsilon}\frac{\operatorname{profit}(x_i)}{\text{LB}}\right\rceil$ and the inner part of the sum $\left\lceil\frac{n}{\epsilon}\frac{\operatorname{profit}(x_i)}{\text{LB}}\right\rceil\le\frac{n}{\epsilon}\frac{\operatorname{profit}(x_i)}{\text{LB}}+1$. Inserting this into the inequality from above, we can continue the proof:
$$ \begin{align*}
\text{OPT}
\le&\frac{\epsilon}{n}\times\text{LB}\times\operatorname{profit}^*(S^*)\\
\le&\frac{\epsilon}{n}\times\text{LB}\times\sum_{x_i\in S^*}\left(\frac{\epsilon}{n}\frac{\operatorname{profit}(x_i)}{\text{LB}}+1\right)\\
=&\operatorname{profit}(S^*)+\frac{\epsilon}{n}\times\text{LB}\times\lvert S^*\rvert
\end{align*} $$ We know the approximate solution set $S^*$ can contain at most $n$ items, so $\lvert S^*\rvert\le n$. Also, $\text{LB}\le\text{OPT}$ because at least the most expensive item fits into the Knapsack.
$$ \begin{align*} \text{OPT}
=&\operatorname{profit}(S^*)+\frac{\epsilon}{n}\times\text{LB}\times\lvert S^*\rvert\\
\le&\operatorname{profit}(S^*)+\epsilon\times\text{LB}\\
\le&\operatorname{profit}(S^*)+\epsilon\times\text{OPT}\\
(1-\epsilon)\times\text{OPT}\le&\underbrace{\operatorname{profit}(S^*)}_{\mathcal{A}_\epsilon(I)}
\end{align*} $$ We have derived $(1-\epsilon)\le\frac{\mathcal{A}_\epsilon(I)}{\text{OPT}}$, which completes the proof.

3.2 Traveling Salesman Problem

The Traveling Salesman Problem (TSP) is of interest because, as opposed to the Knapsack problem, it does not allow for any PTAS, in its most general form. In this section we briefly define the problem and prove why it cannot be approximated unless $\mathit{P}=\mathit{NP}$.

It is noteworthy that, by restricting the TSP instances to the ones where any three nodes in $G$ satisfy the triangle inequality, the problem remains NP-hard but admits PTASs. The Euclidean-TSP is one such TSP-subproblem.

Problem statement. The TSP problem is to compute a route of minimum cost that visits every node of a complete, weighted graph $G$ (which is the problem instance) with non-negative edge costs exactly once. In a complete graph every node has a connection to every other node. The theorem is that there exists no such algorithm $\mathcal{A}_\epsilon$, which finds an approximate solution to TSP with a relative approximation quality guarantee $\epsilon$, unless $\mathit{P}=\mathit{NP}$.

Proof. We prove by contradiction, in that we reduce the NP-complete Hamiltonian cycle problem to TSP and show that it would be solvable in polynomial time, if a polynomial-time approximation for TSP existed.

The Hamiltonian cycle problem is about determining whether or not a cycle exists within a graph $G$ such that each node is visited exactly once. The problem is NP-complete. It can be reduced to TSP in polynomial time by converting the graph $G$ into a new graph $G’$ with the same number of nodes. Let $\lvert V\rvert$ denote the number of nodes. For every edge in the original graph $G$, an edge with cost $1$ is added to the new graph $G’$. After transferring all edges in that manner, we make $G’$ complete (i.e. fully connected) by adding all missing edges with some cost $w\in(1,\infty)$. If the shortest path yielded by the exact TSP algorithm $\mathcal{A}_\epsilon(G’)$ is equal to $n$, a Hamiltonian cycle exists, otherwise there is none.

Assume there was a PTAS with relative approximation guarantee $1+\epsilon$, i.e. the solution found by the algorithm were at most $(1+\epsilon)\times$ the length of the shortest path, which has length $\text{OPT}$. If we performed the conversion from $G$ to $G’$ (Hamiltonian cycle problem to TSP) with the edge cost $w:=(1+\epsilon)\times\lvert V\rvert$, the optimal solution would be $\text{OPT}=\lvert V\rvert$, if a Hamiltonian cycle existed in $G$. The second best solution would have to visit at least one of the newly added edges, thereby increasing the length of the path to some value $\ge(1+\epsilon)\times\lvert V\rvert$. Since the TSP-PTAS guarantees a path length of at most $(1+\epsilon)\times\lvert V\rvert$, it could be used to decide whether $G$ contains a Hamiltonian cycle by checking whether $\mathcal{A}_\epsilon(G’)\le(1+\epsilon)\times\lvert V\rvert$ holds true. The NP-complete Hamiltonian cycle problem, however, cannot be solved exactly by a polynomial-time algorithm so there cannot exist a PTAS for TSP, which completes the proof.

References

Mark de Berg. Lecture 7: Polynomial-time approximation schemes. 2017. URL https://www.win.tue.nl/~mdberg/Onderwijs/AdvAlg_Material/Course Notes/lecture7.pdf.

Thomas Jansen. Introduction to the theory of complexity and approximation algorithms. In Lectures on Proof Verification and Approximation Algorithms. Springer, 1998.

Vijay V. Vazirani. Approximation Algorithms. Springer Science & Business Media, 2013.

Gerhard J Woeginger. When does a dynamic programming formulation guar- antee the existence of a fully polynomial time approximation scheme (fptas)? INFORMS Journal on Computing, 12(1):57–74, 2000.

Choosing a featured image for this post was not easy. The topic is very theoretical so I went with some maps which can be loosely related to the Traveling Salesman problem. I hope that adds up. Credit for the photo goes to Andrew Neel.