ND28 M INIMUM B OUNDED D IAMETER A UGMENTATION

     
• I NSTANCE : Graph , positive integer D<|V| .
• S OLUTION : An augmenting set E' for G , i.e., a set E' of unordered pairs of vertices from V , such that has diameter D , i.e., the maximum distance of any pair of vertices is at most D .
• M EASURE : Cardinality of the augmenting set, i.e., |E'| .

• Bad News: As hard to approximate as M INIMUM S ET C OVER [ 255 ].
• 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 [ 255 ].