MINIMUM K-SWITCHING NETWORK

• INSTANCE: Complete graph $G=\left(V,E\right)$ and distances $d(v_i,v_j)\in N$ satisfying the triangle inequality.

• SOLUTION: A partition $F=\{A_1,A_2,\ldots, A_{k},B_1,B_2,\ldots, B_{k}\}$ of V.

• MEASURE: Maximum distance between vertices in different sets with the same index, i.e.,
  
  $$\max\limits_{i\in[1..k]} \max\limits_{v_1\in A_{i}\atop v_2\in B_{i}} d(v_1,v_2).$$
  
  

  
  

• Good News: Approximable within 3 [254].

• Bad News: Not approximable within 2$-\varepsilon$ for any $\varepsilon >0$ [254].