## 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.