Halmazrendszerek speciálkollégium, Hajnal Péter IX. 30. (1 óra)

Petr Slavik bizonyítása: Adott g ≥ o ≥ 2 esetén mi az a aminimális alaphalmaz, amin megadható olyan halmazrendszer (és

éleinek egy sorbarakása), amelyre a mohó algoritmus g elemű fedést ad, míg az optimum o elemű?

Legyen H egy V feletti halmazrendszer a kérdésben leírt tulajdonságokkal. Legyen s_{1}, s_{2},…, s_{g} a mohó algoritmus által

⋮ |V | ≥ f(g, o).

Megjegyzés: Ez a becslés pontos: Minden olyan V -re, amelyre |V | ≥ f(g, o) megadható egy olyan halmazrendszer, amely fedési optimuma o és a mohó algoritmus g halmazzal fed.

Ebből a

1 ≤ \frac{μ_{mohó,π}H}{μ(H)} ≤ f(|V |)

alakú tételek közül a legjobb f-et maghatározhatjuk.

Lemma: f(|V |) = max\{ \frac{g}{o} : |V | ≥ f(g, o) \}.

Ebből a következő tételek nyerhetők:

Tétel:

1 ≤ \frac{μ_{mohó,π}H}{μ(H)} ≤ ln |V |.

Tétel:

1 ≤ \frac{μ_{mohó,π}H}{μ(H)} ≤ ln |V | − ln ln |V |.

Lineáris programozási becslés

A maximális számú független él meghatározásával ekvivalens egészértékű programozási feladat. Folytonos relaxáció.

Definíció: ν^{∗}(H)

A lefogási feladattal ekvivalens egészértékű programozási feladat. Folytonos relaxáció.

Definíció: τ^{∗}(H)

Az egészértékű és folytonos feladatot összekötő diszkrét feladatok felírása.

Definíció: τ_{k}(H).

ν_{k}(H) hasonlóan definiálható.