Hlavna stranka
Domace ulohy
Rasto Kralovic


Prva domaca uloha

Zadanie: Problem MinPartition je definovany nasledovne: Je dane prirodzene cislo N a mnozina X={x1,....,xN} celych kladnych cisel. Cielom je najst jej rozklad Y1, Y2 tak, ze max{w(Y1),w(Y2)} je minimalne; w(S) oznacuje sucet prvkov v mnozine S
Uvazujme greedy algoritmus, ktory zacina s prazdnymi mnozinami Y1 , Y2 a pridava prvky v poradi od najvacsieho po najmensi vzdy do tej mnoziny, ktora ma momentalne mensi sucet prvkov (ak w(Y1)=w(Y2), prida prvok do lubovolnej mnoziny).
Ukazte, ze uvedeny algoritmus je r-aproximativny a najdite tesnu hodnotu r (t.j. najdite vstup, na ktorom sa dosiahne chyba r).

Riesenie: Tesna hodnota je 7/6. Horny odhad dava napr. algoritmus MinScheduling z nasledujucej prednasky pre specialny pripad p=2. Dolny odhad je na vstupe 3, 3, 2, 2, 2 .

Druha domaca uloha

Zadanie 1: Dokazte, ze problem Max-k-DimensionalMatching je k-aproximovatelny.
Vstup je mnozina M={m1,...,mn}, kde mi=[mi,1,...,mi,k], 0<mi,j<=q
Riesenim je podmnozina mnoziny M taka, ze kazde dva jej prvky sa lisia vo vsetkych suradniciach. Cielom je najst maximalnu taku mnozinu.

Zadanie 2: Najdite FPTAS pre problem MinKnapsack (mame danych n veci, kazda ma danu velkost a cenu. Takisto je dany cenovy limit. Treba vybrat najlahsiu mnozinu veci s celkovou cenou vacsou ako limit)

Tretia domaca uloha

Zadanie 1: Dokazte, ze PCP[O(log n),O(1)] je podmnozina NP.
Zadanie 2: Dokazte, ze PCP[O(log n),1]=P
Zadanie 3: Dokazte nasledujucu vetu: Nech P1, P2 su NPO problemy. Nech P1<=LP2 a P1 je z APX. Potom P1<=APP2