Rendszeroptimalizálás, 17. tétel

Polinomiális approximációs séma a RÉSZÖSSZEG problémára

Polinomiális approximációs séma

• Def.*: egy probléma polinomiális approximációs sémával közelíthető, ha ∀ε>0-ra van rá (1+ε)-approximáció.

Ez nem mindig elég, mert ha a közelítő algoritmus lépésszáma 2^1/εn⁴, még mindig exponenciálisan hosszú ideig fut.

• Def.*: egy probléma teljesen polinomiális approximációs sémával közelíthető, ha ∀ε>0-ra van rá (1+ε)-approximáció, ami 1/ε-ban is polinomiális.
  
• Pl.*: a metrikus utazó ügynök problémára nincs P approximációs séma, de az euklideszi utazó ügynök problémára van teljesen P approximációs séma.

Részösszeg probléma

Adott _A_ = {a₁, a₂, ..., a_n} és _t_.
Kérdés: létezik-e B⊆A úgy, hogy Σb_i = _t_?
Speciális eset: partíció probléma, amikor _t_ = Σa_i/2, még ez is NP-teljes.

Részösszeg optimalizálási probléma

Adott _A_ = {a₁, a₂, ..., a_n} és _t_.
Keressük B⊆A-t úgy, hogy Σb_i maximális és Σb_i ≤ _t_ legyen.
A feladat NP nehéz, mert a részösszeg probléma visszavezethető rá. Bizonyítás: ha találunk olyan a _B_ halmazt, amire Σb_i = _t_, akkor igen a válasz a részösszeg problémára, különben nem.
A feladat nem NP-beli, mert nem eldöntési probléma, tehát nem is NP-teljes.

Közelítő algoritmus a részösszeg optimalizálási problémára

• Tétel*: a probléma teljesen polinomiális sémával közelíthető.

A bizonyítás egy konkrét algoritmus lesz:

1. Pontos megoldást adó algoritmus: Tegyük fel, hogy a₁ ≤ a₂ ≤ ... ≤ a_n. Definiálunk két halmazsorozatot:
   • L₀ = {0}
   • L_i' = {l+a_i | l∈L_i}
   • L_i+1 = L_i ∪ L_i'
   Röviden: L_i+1 = L_i ∪ (L_i+a_i+1) Például:
   • a₁=3, a₂=5, a₃=7
   • L₀ = {0}
   • L₀' = {3}, L₁ = {0,3}
   • L₁' = {5,8}, L₂ = {0,3,5,8}
   • L₂' = {7,10,12,15}, L₃ = {0,3,5,7,8,10,12,15}
   Az optimális részletösszeg max{l|l∈L_n ∧ l≤t} lesz.
2. Polinomiális közelítő algoritmus: Egyrészt vegyük észre, hogy az L_i' halmazokból nincs szükségünk a t-nél nagyobb elemekre. Képezzük a halmazokat a következő módon: L_i' = (L_i+a_i) ∩ [0..t]. Def.: δ-val ritkítás

   <i>L</i> növekvő sorrendbe rendezett halmaz.
   foreach (l'''∈L''') {
   	''m'' az ''l''-et megelőző, halmazban hagyott elem, vagy ha nincs ilyen, 0.
   	if (''l''lt;m(1+''δ'')) ''l''-et kidobjuk.
   }

   A ritkítás után bármely két szomszédos elem hányadosa legalább 1+δ. A ritkított halmaz mérete felülről becsülhető: |L_ritkított ≤ log_1+δt+2.

3. *Tétel*: ha az algoritmus során a halmazok t-nél nagyobb elemeit minden lépésben levágjuk és az eredményt δ=ε/2n-vel ritkítjuk, (1+ε)-approximációt kapunk a problémára, és a lépésszám n-ben, log t-ben és 1/ε-ban is polinomiális lesz.
   • Biz.*: az algoritmus (1+ε)-approximációs. %P%
   • Biz.*: az algoritmus lépésszáma mindhárom mennyiség szerint polinomiális.
   [math] \forall i \: |L_i| \le \log_{1+\frac{\epsilon}{2n}}t+2 = \frac{\ln t}{\ln (1+\frac{\epsilon}{2n})}+2 = O(\log t) [/math] Másrészt az x≥-1-re érvényes x/(1+x) ≤ ln(1+x) összefüggést kihasználva x=ε/2n helyettesítéssel: [math] \forall i \: |L_i| \le \frac{\ln t}{\ln (1+\frac{\epsilon}{2n})}+2 \le \frac{(1+\epsilon/2n) \ln t}{\epsilon/2n}+2 = \frac{(2n+\epsilon) \ln t}{\epsilon}+2 [/math] Az algoritmus során n db lista összefésülést kell végezni, aminek a komplexitása O(∑|L_i||) = O(n||L_i||). A fenti becslések alapján látszik, hogy O(n||L_i) n-ben négyzetes, log(t)-ben lineáris, tehát mindkettőben polinomiális. Az 1/ε szerinti becslést órán lenyeltük. %P%

-- Peti - 2006.12.18.