Cheapest network on four servers
Four servers are joined pairwise by 6 possible links, and each link has an independent Uniform cost. You build the cheapest set of links that connects all four servers (a minimum spanning tree, which uses 3 links). What is its expected total cost? Give four decimals.
Show hints (2)+
- Use Kruskal's algorithm. Which sets of three cheapest links do not form a spanning tree?
- The -th smallest of 6 uniforms has mean , and the ranking is independent of the values.
Answer
Reveal answer →Final answer
0.8857 (± 0.001)
Create a free account to see the full worked solution and track your progress.
Interview format: Hedge Fund Quant, Prop Trading