Polynomial-time Approximation Schemes (PTAS)

Timo I. Denk, TINF16B1, DHBW Karlsruhe

Theoretical CS Seminar (April 12, 2019)

Slides available at timodenk.com/talks/ptas

Outline

1. Background and motivation
2. PTAS and FPTAS definition
3. FPTAS for the Knapsack problem
4. PTAS and the Traveling Salesman problem
5. Summary
6. Questions

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

TypeRuntimeExact
Naive$\mathcal{O}\mathopen{}\left(2^n\right)\mathclose{}$
Dynamic programming$\mathcal{O}(nP)$
Greedy$\mathcal{O}(n\log n)$fixed rel. guarantee
FPTAS$\mathcal{O}\mathopen{}\left(\frac{n^3}{\epsilon}\right)\mathclose{}$choosable rel. guarantee $\epsilon$

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}$

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)$

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

• Mark de Berg. Lecture 7: Polynomial-time approximation schemes. 2017.
• 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 guarantee the existence of a fully polynomial time approximation scheme (fptas)? INFORMS Journal on Computing, 12(1):57–74, 2000.