Rendszeroptimalizálás, 15. tétel

Ez az oldal a korábbi SCH wiki-ről lett áthozva. Az eredeti változata itt érhető el.

Ha úgy érzed, hogy bármilyen formázási vagy tartalmi probléma van vele, akkor kérlek javíts rajta egy rövid szerkesztéssel.

Ha nem tudod, hogyan indulj el, olvasd el a migrálási útmutatót

!! Additív hibával közelítő algoritmus fogalma, példák. Relatív hibával közelítő algoritmusok, példák: minimális lefogó ponthalmaz, halmazfedés.

Additív hibával közelítő algoritmus

• Def.*: egy algoritmus C additív hibával közelítve old meg egy minimalizálási problémát, ha minden I inputra polinomiális időben ad egy y_I-t, amire

[math] f(y_I) \le \min\limits_{x \in X_I} f(x)+C [/math] vagy [math] f(y_I) \ge \max\limits_{x \in X_I} f(x)-C [/math] maximalizálási probléma esetén.

• Példák*:
• Élkromatikus szám keresése. A Vizing-tétel szerint Δ(G)≤χ_e(G)≤Δ(G)+1, és a bizonyítás algoritmikus.
• Síkbarajzolható gráfok színezése. Polinom időben eldönthető, hogy színezhető-e 2 színnel. A színezés 3 színnel NP-teljes, 4 színnel nem ismert (a négyszíntétel bizonyítása nem algoritmikus). 5 színnel minden gráf színezhető polinomiális idő alatt ⇒ létezik 2 additív hibával közelítő algoritmus a problémára.

• Lemma*: van olyan probléma, ami nem közelíthető additív konstanssal.
• Biz*: leghosszabb kör keresése C hibával visszavezethető a Hamilton-kör keresésére úgy, hogy a G gráf minden élét C+1-felé bontjuk. A kapott G'-ben ha a közelítő algoritmus talál |V(C+1) hosszú kört, G-ben volt Hamilton-kör, különben nem.

Multiplikatív hibával közelítő algoritmus

• Def.*: egy algoritmus k-approximációs, ha egy minimalizálási probléma minden I inputjára polinom időben ad egy y_I megoldást, amire

[math] f(y_I) \le k \min\limits_{x \in X_I} f(x) [/math]

• Példa*: τ(G) minimális lefogó ponthalmaz keresése: egy nem bővíthető párosítás éleinek vesszük a végpontjait. τ(G)≥ν(G) és ≤2ν(G) méretű megoldást találtunk ⇒ az algoritmus 2-approximációs.

Függvény hibával közelítő algoritmus

• Példa*: halmazfedés. Adott U alaphalmaz, S₁⊆U, ..., S_n⊆U részhalmazai és c:{S_i}→R⁺ költségfüggvény. Keressük a minimális összköltségű fedést.
  
• Algoritmus*:
• C⊆U az U halmazból már lefedett elemek részhalmaza.
• while (C!=U) válasszuk azt az S_i halmazt, amire c(S_i)/|S_i-C minimális.
• Lemma*: legyen p(e)=c(S_i)/|S_i-C||, ahol S_i az a halmaz, ami az algoritmus során először fedte le e-t. e₁, ..., e_m (m=||U) az elemek az algoritmus során kapott lefedési sorrendben. p(e_k)≤OPT/(m-k+1).
  
• Biz.*: ∑p(e) = fedés összköltsége. Mivel az algoritmus mindig a minimális c(S_i)/|S_i-C értékű halmazt választja,
  

p(e_k) = c(S_i)/|S_i-C|| ≤ OPT/||C = OPT/(m-k+1)

• Köv.*: a fedés költsége ≤ OPT/1+OPT/2+...+OPT/m < OPT*ln(m).

-- Peti - 2007.01.02.