Test 3 - 6.5.2014

Čas cca 40min.

-Bratley’s algorithm(tree)
r=[5,0,4,0]
p=[3,2,2,1]
d=[10,3,10,2]

a) nakreslit strom a Ganttuv diagram
b) je to optimalni reseni? Proc?

-2-aproximation alg for knapsack a) popsat pomoci pseudokodu
b) dukaz, ze aprox koef je 2

Bratley

• r=[1,8,2,0]
• p=[2,1,2,3]
• d=[6,9,7,6]

Christofidesův algoritmus

• Popsat pseudokódem
• Jaký má aproximační faktor