6. Közelítő algoritmusok 2

Megj.: Lehet hogy egy altalanosan nehez feladatot kapunk, de ha valami spec esetet akarunk megoldani akkor lehet hogy meg lehet oldani polinomialis idoben.

Kozelito megoldasok

A kovetkezok adottak:

• $x$ input $\mapsto X(x)$ megengedett megoldasok halmaza
• $f_x:X(x)\to \mathbb{R}$ kiertekelesi fuggveny

Feladat: keressunk $y\in X(x)$ megengedett megoldast, amire $f_x(y)$ minimalis.

Def.: Egy $A$ algoritmust $\alpha$-kozelitonek hivunk, ha $\forall x$ inputra, melyre $X(x)\ne \varnothing$, kiad egy $y\in X(x)$ -et, melyre $f_x(y)\le \alpha \cdot \text{OPT}$.
Ahol $\text{OPT}$ azt a megoldast jeloli amire $f_x(y)$ minimalis.

Megj.: Ha maximumot keresunk akkor $f_x(y)\ge \frac{1}{\alpha }\cdot \text{OPT}$

Egyszeru peldak:

1. Adott $G$ iranyitott graf, keressunk $E^{\prime }\subseteq E$ reszgrafot, ami aciklikus es $|E^{\prime }|$ maximalis.
   $2$-kozelites konnyen elerheto a kovetkezo modon:
   Szamozzuk meg a csucsokat es legyen $E_1$ az elore elek halmaza es $E_2$ a vissza elek halmaza. Nyilvan egyik sem tartalmaz kort mert mindketto topologikusan van rendezve. Mivel $E_1\cup E_2=E$ ezert

$$\max (|E_1|,|E_2|)\ge \frac{|E|}{2}$$

2. Adott $G$ iranyitatlan graf, keressuk $\tau (G)$-t legkisebb lefogo csucshalmaz
   $2$-kozelito algoritmus:
   Legyen $M$ egy nem bovitheto parositas. Ekkor

$$|M|\le \tau (G)\le 2|M|$$

Igy ez nyilvan egy $2$-kozelito algoritmus.

Metrikus utazo ugynok

Input: $G$ graf, $c:E\to {\mathbb{R}}^{+}$

Def.: Egy tura egy olyan seta amely minden csucsot legalabb egyszer erint.

Feladat: Egy minimalis koltsegu turat talalni.

$2$-kozelito algoritmus a metrikus utazo ugynok feladatra:

1. Keressuk meg a $T$ minimalis koltsegu feszito fat
2. $T$-bol kepzunk egy $2\cdot c(T)$ koltsegu turat ugy, hogy a $T$ feszito fat bejarjuk ugy. Ekkor minden elen pontosan ketszer fogunk atmenni.
   Ekkor belathato a kovetkezo:

$$c(T)\le \text{OPT}\le 2\cdot c(T)$$

Def.: Az $A$ algoritmus $\epsilon$ relativ hibaval kozelit, ha $(1+\epsilon )$-kozelito
Megj.: max: $\frac{1}{1+\epsilon }\approx 1-\epsilon$

Def.: Polinomial Time Approximation Scheme (PTAS)
Minden $\epsilon >0$ -hoz adunk egy $A_{\epsilon }$ polinomialis algoritmust, ami $\epsilon$ relativ hibaval kozelit.

Def.: Fully PTAS (FPTAS)
Letezik $A$ algoritmus $\epsilon$ relativ hibaval

$$O\left(\text{poli}\left(\frac{1}{\epsilon },n\right)\right)$$

Def.: Efficient PTAS (EPTAS)
Letezik $A$ algoritmus $\epsilon$ relativ hibaval

$$O\left(f\left(\frac{1}{\epsilon }\right)\cdot n^c\right)$$

Hatizsak feladat (again)

Dinamikus Programozas algoritmus

Tudunk egy felso korlatot adni az optimum-ra: $E\ge \text{OPT}$.
Peldaul $E=\sum e_i$ de ennel tudnk jobbat is adni.

$\forall i$ $\forall e\le E$ kiszamoljuk, hogy mi a legkisebb hatizsak, amibe ki tudunk vinni $e$ erteket az elso $i$ targy kozul.

T(0, 0) = 0
FOR j = 1 .. E:
	T(0, j) := W + 1  // ez jeloli, hogy nem tudunk kivinni

FOR i = 1 .. n:
	FOR j = 0 .. E:
		T(i, j) := T(i-1, j)
	FOR j = e_i .. E:
		IF T(i-1, j-e_i) + w_i < T(i, j) THEN
			T(i, j) := T(i-1, j-e_i) + w_i

FOR j = E .. 0 (-1):
	IF T(n, j) <= W THEN
		e := j
		j := 0

I := {}  // a kivitt targyak halmaza
FOR i = n .. 1 (-1):
	IF T(i, e) < T(i-1, e) THEN
		I := I U {i}
		e := e - e_i

$O(n\cdot E)$ de ez nem polinomialis, mert az input a targyak sulyai es ertekei amik szamjegyekkel vannak megadva. Tehat az input merete $O\left(\sum \log w_i+\sum \log e_i\right)$

Ibarra–Kim approximációs algoritmusa

Legyen adva $n$ darab tárgy pozitív egész $w_i$ súlyokkal és $e_i$ értékekkel, valamint egy $w$ súlykorlát, továbbá egy $\epsilon >0$ pontossági korlát. Tegyük fel, hogy minden $i$-re $w_i\le w$, hiszen a súlykorlátnál nehezebb tárgyakat úgysem vihetnénk magunkkal. Legyen

$$\mathrm{OPT}=\max \left\{\sum _{i\in I}{e}_i\mid I\subseteq \{1,2,\dots ,n\}\text{ eˊs }\sum _{i\in I}{w}_i\le w\right\}$$

valamint legyen $I^{\ast }$ egy olyan részhalmaz, amire a maximum éppen eléretik.

Legyen most $M$ egy késöbb alkalmasan választandó szám, ezzel készítsük el a $w_i^{\prime }=w_i,e_i^{\prime }=\lfloor e_i/M\rfloor$ súlyokat és értékeket, erre a dinamikus programozási algoritmussal keressük meg a $w$ méretű hátizsákban elvihető legnagyobb értéket, legyen ez OPT’. Ezen optimum vétessen fel valamely $J$ részhalmazon, ezt egyébként a dinamikus programozási algoritmussal visszalépéssel (minden minimumszámításnál annak megjegyzésével, hogy a két tag közül melyik eredményezi a minimumot) ki lehet számítani.

Elöször is vegyuik észre, hogy

$$\frac{e_i}{M}-1\le \lfloor \frac{e_i}{M}\rfloor \le \frac{e_i}{M}$$

valamint hogy $I^{\ast }$ optimális valsztása miatt

$${\mathrm{OPT}}^{\prime }=\sum _{i\in J}\lfloor \frac{e_i}{M}\rfloor \le \frac{1}{M}\sum _{\mathrm{i}\in J}{e}_i\le \frac{1}{M}\mathrm{OPT}$$

Másfelol a $J$ optimális volta miatt

$${\mathrm{OPT}}^{\prime }=\sum _{i\in J}{e}_i^{\prime }\ge \sum _{i\in I^{\ast }}{e}_i^{\prime }\ge \sum _{i\in I^{\ast }}\frac{e_i}{M}-1\ge \frac{1}{M}\sum _{i\in I^{\ast }}{e}_i-n=\frac{1}{M}\mathrm{OPT}-n.$$

Ezek alapján tehát látjuk, hogy

$$\mathrm{OPT}-nM\le M\cdot {\mathrm{OPT}}^{\prime }\le \mathrm{OPT}$$

most még megmutatjuk, hogy $nM\le \epsilon \cdot OPT$, ezzel azt fogjuk látni, hogy

$$(1-\epsilon )\mathrm{OPT}\le M\cdot {\mathrm{OPT}}^{\prime }\le \mathrm{OPT}$$

azaz az algoritmusból adódó $M\cdot OP{T}^{\prime }$ a valódi optimumnak legfeljebb $\epsilon$ hibájú becslése.

Megadjuk végül $M$ értékét. Legyen $E={\sum }_{i=1}^n{e}_i$, ezzel legyen

$$M=\frac{\epsilon E}{n^2}$$

ekkor

$$nM=\epsilon \frac{E}{n}\le \epsilon \underset{1\le i\le n}{\max }{e}_i\le \epsilon \mathrm{OPT},$$

hiszen az átlag nem nagyobb a maximumnál valamint bármelyik konkrét egyetlen tárgyat önmagában el tudjuk vinni.

Már csak az algoritmus lépésszáma van hátra, ez

$$O\left(n\sum _{i=1}^n{e}_i^{\prime }\right)\le O\left(n\sum _{i=1}^n\frac{e_i}{M}\right)\le O\left(\frac{nE}{M}\right)\le O\left(\frac{n^3}{\epsilon }\right)$$

ami valóban polinomiális approximációs algoritmust jelent.