Skip to content
Get started

Cheapest network on four servers

Four servers are joined pairwise by 6 possible links, and each link has an independent Uniform(0,1)(0,1) 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)+
  1. Use Kruskal's algorithm. Which sets of three cheapest links do not form a spanning tree?
  2. The kk-th smallest of 6 uniforms has mean k/7k/7, and the ranking is independent of the values.

Answer

Reveal 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

Related questions