MINIMUM DIAMETERS DECOMPOSITION

• INSTANCE: Graph $G=\left(V,E\right)$.

• SOLUTION: A decomposition of the graph into two factors, $F_1$ and $F_2$, with equal diameters.

• MEASURE: The diameter of $F_1$.

  
  

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

• Comment: Variation in which the diameters of $F_1$ and $F_2$ do not need to be equal, and where the objective is to minimize the sum of the diameters, is not approximable within 5/4$-\varepsilon$ [406].