Fórum studentů MFF UK

Oproti loňským letům díky lehké reorganizaci zmizelo pár příkladů řešených na cvičení a oproti tomu přibyla hromada jiných. Nemáte hinty jak na ně?

5. cvičení
1.Nechť máme k dispozici „černou skřínku“, která umí řešit rozhodovací verzi problému součtu podmnožiny v polynomiálním čase. Skřínka odpovídá pouze ANO-NE. Zkonstruujte algoritmus, který pro daný vstup optimalizační verze problému součtu podmnožiny najde v polynomiálním čase (vzhledem k délce binárního zápisu vstupních dat) optimální řešení.
2.Popište jak lze pro libovolné dané n zkonstruovat graf na n vrcholech takový, že aproximační algoritmus pro vrcholové pokrytí s poměrovou chybou r=2 (prezentovaný na přednášce) na tomto grafu vrací pokrytí právě dvakrát větší než je velikost optimálního vrcholového pokrytí (tj. ukažte, že dokázaný odhad poměrové chyby je těsný).
3.Navrhněte algoritmus, který v polynomiálním čase nalezne optimální vrcholové pokrytí pro neorientovaný graf bez cyklů (les, strom).
4.Bottleneck TSP: vstupem je úplný ohodnocený neorientovaný graf s nezápornými váhami na hranách (stejně jako u obyčejného TSP), o kterých navíc předpokládáme, že splňují trojúhelníkovou nerovnost. Úkolem je opět najít nejkratší Hamiltonovskou kružnici ve vstupním grafu, ovšem délka kružnice není v tomto případě rovna součtu délek hran na kružnici, ale maximu z délek hran na kružnici. Nejdříve dokažte, že Bottleneck TSP je NP-těžký a poté navrhněte polynomiální aproximační algoritmus s poměrovou chybou r=3.

1.)suma x_i <= t, black box nam povie ano, ak existuje S_i: suma x_i cez prvky S_i = t
ide tam o pridavanie y₀ = 2⁰, y₁ = 2¹, ... y_{log_2 t} = 2^{log_2 t} (tie log s dolnou celou castou), potom nasu instanciu tvoria x_j, y_i a t a pytame sa, ci sa da t poskladat z y_i... presne som to nepochopil, doplnte ma niekto...

2.) hviezda -- jeden vrchol v strede spojeny so vsetkymi vrcholmi usporiadanymi do kruhu okolo stredu... algoritmus vyberie nahodnu hranu a odstrani jej 2 vrcholy... pritom optimalne VP je tvorene len tym stredom... alebo nejaka modifikacia grafu tvoreneho dvojicami vrcholov spojenymi hranou, cosi ako len tam treba vymysliet co s neparnym poctom...

3.) ideme od listov, tie neofarbime, ale ofarbime ich rodicov, potom odstranim hrany veduce medzi listami a ich rodicmi aj s danymi vrcholmi a iterujem... ofarbene vrcholy by mali byt potom VP... spravnost sa da dokazat podobne ako spravnost algoritmu B na prednaske, hrany su po 2 disjunktne, vybrana nemoze byt incidentna s inou potom...

hadam ma ostatni doplnia...

4) BottleneckTSP
prevod HK BTSP skoro stejnej, jako u normalniho TSP: nehrany ohodnotim 2, hrany 1 a ptam se, jestli existuje kruznice vahy 1. Aproximacni algoritmus se zase dela pres min. kostru, vyuziju fakt, ze "G je souvisly G³ je hamiltonovsky" a z trojuhelnikovy nerovnosti pak plyne, ze kruznice nebude delsi, nez trojnasobek minimalni kostry.