Some problems are too hard to solve exactly, so we settle for an Ī±-approximation: a solution provably within a factor Ī± of the optimum. Play against two approximation algorithms from ALG 19.6. Then see, on your own instance, why their guarantees hold. Each round gives up to 100 points: 100 Ć (how close you got to the optimum).
Cities are points in the plane and ā(x,y) is their distance, so the triangle inequality holds. Click the cities to plan a Hamiltonian cycle that starts and ends at the yellow home city a. The algorithm walks around a minimum spanning tree. Can you beat it? Can you hit the optimum?
your tour 0
round 1/5
score 0
best 5-round score ā
The algorithm (ALG 19.6): find a minimum spanning tree, root it at a, traverse it by depth-first search. That walk uses every tree edge twice. Then skip every vertex visited before and jump straight to the next unvisited one.
Finish your tour to see the algorithm and the optimum on this map.
Items have weights hi and values ci. The knapsack holds weight H. Click items to pack the most valuable set P with h(P) ā¤ H. The values are large, so the exact O(nC) dynamic programming would be slow. ApproxKnapsack rounds the values to small numbers first. How much does that cost it?
weight 0 / 0
value 0
round 1/5
score 0
best 5-round score ā
Choose Īµ:
Also in ALG 19.6: with a somewhat more complicated trick, metric TSP can be 1.5-approximated. Without the triangle inequality, a polynomial t-approximation for anyt ā„ 1 would give P = NP (give the edges of a graph length 1 and all non-edges a huge length c). Knapsack, on the other hand, has an FPTAS: ApproxKnapsack runs in time O(n3/Īµ).