Approximations Algorithmus anhand des Rucksackproblems

Es stellt sich raus, dass das Rucksackproblem ein NP vollständiges Problem ist. Somit ist eine Lösung des Problems wahrscheinlich nicht in polynomieller Laufzeit möglich. Es gibt aber Algorithmen, welche das Problem approximieren und so in besserer Laufzeit zu einem Ergebnis kommen, welches der eigentlichen Lösung des Problems sehr nahe ist.

Der Approximative Algorithmus nimmt folgende Input Werte: $w_i,p_i,W\in \mathbb{N}$
Des Weiteren wird die folgende Annahme getroffen: Alle $w_i\le W$
Diese Annahme ist aber harmlos, wenn $w_i>W$ ist, kann es ohnehin nicht verwendet werden.

Ausserdem gilt: $P_{opt}\ge p_{max}$ wobei $P_{opt}$ der Profit der optimalen Lösung ist und $p_{max}$ das maximale $p_i$

Das Ziel des Algorithmus ist es nun eine Lösung zu finden, welche fast optimal ist und in polynomineller Zeit gefunden werden kann.

Die Idee um das zu erreichen ist es zu runden.

Dazu wird $p_i$ durch ${\tilde{p}}_i$ ersetzt, wobei ${\tilde{p}}_i$ folgendermassen definert ist:

$${\tilde{p}}_i:=k\cdot \lfloor \frac{p_i}{k}\rfloor k\in \mathbb{N}$$

$w_i$ und $W$ bleiben unverändert $\to$ die selben Teilmengen wie davor passen in den Rucksack.

Beispiel

$k=10$ , Profite $p_i$: $112,78,1001,17,237$
Die gerundeten Profite ${\tilde{p}}_i$ : $110,70,1000,230$

Aus der Anwendung des Rundens folgen nun die folgenden Beobachtungen:

$$\begin{array}{rl}{p}_i-k& \stackrel{(1)}{\le }{\tilde{p}}_i\stackrel{(2)}{\le }{p}_i\le p_{\max }\stackrel{(3)}{\le }{P}_{\mathrm{opt}}\le P\stackrel{(4)}{\le }n\cdot p_{\max }\end{array}$$

Daraus folgen nun die folgenden beiden Varianten:

• $p_i\stackrel{\mathrm{DP}}{\to }OPT\subseteq \{1,\dots ,n\}$ , Profit $P_{opt}$, Laufzeit: $O(n\cdot P)$ (zu langsam)
• ${\tilde{p}}_i\stackrel{\mathrm{DP}}{\to }\widetilde{OPT}\subseteq \{1,\dots ,n\}$ , Profit ???, Laufzeit: $O(\frac{n\cdot \tilde{P}}{k})\le O(\frac{n^2\cdot p_{max}}{k})$

$\tilde{P}={\tilde{p}}_1+\dots +{\tilde{p}}_n$

Die Ungleichung: $O(\frac{n\cdot \tilde{P}}{k})\le O(\frac{n^2\cdot p_{max}}{k})$ gilt, da $\tilde{P}={\sum }_{i=1}^n{\tilde{p}}_i\le {\sum }_{i=1}^n{p}_i\stackrel{(4)}{\le }n\cdot p_{\max }$.

Es stellt sich nun allerdings die Frage, wie gut sich $\widetilde{OPT}$ für das ursprüngliche Rucksackproblem eignet.

$\widetilde{OPT}$ wird daher untersucht um festzustellen, wie gut es sich eignet.

Es ist bekannt, das $\widetilde{OPT}$ das Optimum für ${\tilde{p}}_i$ ist.
Für jede Teilmenge $I$, welche in den Rucksack passt gilt:

$$\sum _{i\in \widetilde{OPT}}{\tilde{p}}_i\ge \sum _{i\in I}{\tilde{p}}_i$$

Das gilt auch für $I=OPT$:

$$\sum _{i\in \widetilde{OPT}}{\tilde{p}}_i\ge \sum _{i\in OPT}{\tilde{p}}_i\text{\hspace{1em}(*)}$$

Daraus folgt dann:

$$\begin{array}{rl}\sum _{i\in \widetilde{OPT}}{p}_i& \stackrel{(2)}{\ge }\sum _{i\in \widetilde{OPT}}{\tilde{p}}_i\\ & \stackrel{(\ast )}{\ge }\sum _{i\in OPT}{\tilde{p}}_i\\ & \stackrel{(1)}{\ge }\sum _{i\in OPT}(p_i-k)\\ & \ge \left(\sum _{i\in OPT}{p}_i\right)-nk\\ & =P_{\mathrm{opt}}-nk\\ & \stackrel{(3)}{\ge }{P}_{\mathrm{opt}}-nk\cdot \frac{P_{\mathrm{opt}}}{p_{\max }}\\ & =P_{\mathrm{opt}}\cdot \left(1-\frac{nk}{p_{\max }}\right)\end{array}$$

Die Idee ist nun, dass ein (kleines) $ϵ>0$ gewählt wird und $k=\frac{\epsilon \cdot p_{max}}{n}$ gesetzt wird.
(Eigentlich müsste $k=\lceil \frac{\epsilon \cdot p_{\max }}{n}\rceil$ stehen, da $k\in \mathbb{N}$ ist. Einfachheitshalber wird die Rundung aber weggelassen.)

Daraus folgt nun:

$$\Rightarrow \mathrm{PROFIT}(\widetilde{OPT})=\sum _{i\in \widetilde{OPT}}{p}_i\ge P_{\mathrm{opt}}\cdot (1-\epsilon )$$

Da $\epsilon$ klein ist, ist die Lösung fast so gut wie $P_{opt}$.

Die Laufzeit ist nun:

$$O\left(\frac{n^2{p}_{\max }}{k}\right)\le O\left(\frac{n^2{p}_{\max }}{\epsilon \cdot p_{\max }/n}\right)\le O\left(\frac{n^3}{\epsilon }\right)$$

Also ist die Laufzeit polynominell in $n\text{ und }\frac{1}{\epsilon }$