MINIMUM BOUNDED DIAMETER AUGMENTATION

• INSTANCE: Graph $G=\left(V,E\right)$, positive integer $D<\vert V\vert$.

• SOLUTION: An augmenting set E' for G, i.e., a set E' of unordered pairs of vertices from V, such that $G'=\left(V,E \cup E'\right)$ has diameter D, i.e., the maximum distance of any pair of vertices is at most D.

• MEASURE: Cardinality of the augmenting set, i.e., $\vert E'\vert$.

  
  

• Bad News: As hard to approximate as MINIMUM SET COVER [355].

• Comment: Variation in which the size of the augmenting set is bounded by D and the problem is to minimize the diameter is approximable within $4+2/\mbox{\sl opt}$ [355].