Background and Motivation

Complexity Classes

• Polynomial-time algorithms: $\mathit{P}$
• Nondeterministic polynomial-time algorithms: $\mathit{NP}$

PTAS Description

Polynomial-time approximation schemes

Approximate solutions to $\mathit{NP}$-hard problems in $\mathit{P}$ time

Notation

• Optimization problem: $\Pi$
• Instances of the problem: $I\in D_\Pi$
• Size of an instance: $n=\lvert I\rvert$
• Approximation algorithm: $\mathcal{A}$

Objective Function Value

Solution for $I$ has an objective function value $\in\mathbb{R}^+$
Example: length of the path found for a TSP instance

• Algorithm result: $\mathcal{A}(I)$
• Best possible result: $\text{OPT}(I)$

PTAS and FTPAS Definition

Polynomial-time Approximation Scheme (PTAS)

Algorithm $\mathcal{A}_\epsilon$ with polynomial runtime in $n$

$$\forall I\in D_\Pi \left[ \frac{\mathcal{A}_\epsilon(I)}{\text{OPT}(I)}\le1+\epsilon \right]$$

Approximation quality $\epsilon\in(0,\infty)$; $\Pi$ is a minimization problem

Fully Polynomial-time Approximation Scheme (FPTAS)

PTAS with polynomial runtime in $n$ and $\frac{1}{\epsilon}$

$$\mathcal{O}\left(n^\alpha\times\frac{1}{\epsilon^\beta}\right)$$
with $\alpha,\beta\ge1$

PTAS but not FTPAS (examples): $\mathcal{O}(n^\frac{1}{\epsilon})$ or $\mathcal{O}(n^{\frac{1}{\epsilon}!})$

Example: Knapsack Problem

Knapsack: Algorithms

Knapsack: DP Algorithm (1)

Denoted by knapsack_dp

Takes a weight limit $W$ and a set of objects $X=\{x_1,\dots,x_n\}$

Each $x_i$ has a $\operatorname{weight}(x_i)\in\mathbb{Z}^+\le W$ and a $\operatorname{profit}(x_i)\in\mathbb{Z}^+$

Knapsack: DP Algorithm (2)

Outputs the exact solution $\text{OPT}$ in runtime

$$\mathcal{O}(nP)$$

where $n=\lvert X\rvert$, $P:=\operatorname{profit}(X)=\sum_{x_i\in X}\operatorname{profit}(x_i)$

Knapsack: FPTAS (1) Overview

          def knapsack_fptas(weights, profits, W):

              scaled_profits = [ceil(p/sigma) for p in profits]

              approx_solution = knapsack_dp(weights, scaled_profits, W)

              return approx_solution
      

1. Downscales all weights by some $\sigma\in\mathcal{R}^+$
2. Passes the problem with scaled profits to knapsack_dp
3. Returns the approximate results

Knapsack: FPTAS (2) Downscaling Intuition

knapsack_dp runs in $\mathcal{O}(nP)$

Reducing $P$ is achieved by downscaling by $\sigma$ and rounding up:
$$\operatorname{profit}^*(x_i):=\left\lceil\frac{\operatorname{profit}(x_i)}{\sigma}\right\rceil$$

Knapsack: FPTAS (3) Choosing $\sigma$

Lower bound: $\text{LB}=\max_i\operatorname{profit}(x_i)$

$$\operatorname{profit}^*(x_i)=\left\lceil\frac{n}{\epsilon}\frac{\operatorname{profit}(x_i)}{\text{LB}}\right\rceil\in\left\{1,\dots,\left\lceil\frac{n}{\epsilon}\right\rceil\right\}$$

Each profit is $\le\left\lceil\frac{n}{\epsilon}\right\rceil$

Knapsack: FPTAS (4) Runtime

Upper bound of $P$: $P\le n\times\left\lceil\frac{n}{\epsilon}\right\rceil$
$P:=\operatorname{profit}(X)=\sum_{x_i\in X}\operatorname{profit}(x_i)$

$$\mathcal{O}\left(n\times n\times\left\lceil\frac{n}{\epsilon}\right\rceil\right)\subseteq\mathcal{O}\left(\frac{n^3}{\epsilon}\right)$$

Both $n$ and $\epsilon$ occur polynomially ⇒ FPTAS

Knapsack: Error Bound Proof

See Section 3.1 in the accompanying document
timodenk.com/arxiv/201904-ptas.pdf

Example: Traveling Salesman Problem (TSP)

TSP: Definition

Given a complete, weighted graph with non-negative edge costs, find a route that visits every node exactly once with minimum cost.

$\text{OPT}$ is the cost of the best path

TSP: Problem Statement

TSP does not admit a PTAS unless $\mathit{P}=\mathit{NP}$

Proof by contradiction

Hamiltonian Cycle Problem

Decision problem, input graph $G$

Whether a cycle exists such that each node is visited exactly once

Reduction to TSP

Convert graph $G$ (Hamiltonian) to $G'$ (TSP input):

1. Copy all nodes (from $G$ to $G'$)
2. Copy all edges and assign cost $1$ to them
3. All all missing edges to make $G'$ complete; cost $w\in(1,\infty)$

TSP: Proof by Contradiction

Suppose there was a PTAS with approximation guarantee $1+\epsilon$

With $w=(1+\epsilon)\times\lvert V\rvert$, the TSP-PTAS could be used to decide the Hamiltonian cycle problem in polynomial time.
Number of nodes: $\lvert V\rvert$

Summary

PTAS

• Solve NP-hard problems in polynomial time
• Make guarantees about the maximum error
• FPTAS are polynomial in both $n$ and $\epsilon$

Example Problems

• Knapsack is well-tempered and admits FPTASs
• TSP does not even admin PTASs

References

Questions