INSTANCE:
Complete graph
,
weight
for each
,
requirement
for each pair of
vertices from V.
SOLUTION:
A spanning tree for G.
MEASURE:
The weighted sum over all pairs of vertices of the cost of
the path between the pair in T, i.e.,
,
where W(u,v)
denotes the sum of the weights of the edges on the path joining
u and v in T.
Good News:
Approximable within
if the weight
function satisfies the triangle inequality [397].
Comment:
MINIMUM ROUTING COST SPANNING TREE, the variation in which
for all u,v, admits a PTAS [469].
,
weight 
for each
,
requirement
for each pair of
vertices from V.
,
where W(u,v)
denotes the sum of the weights of the edges on the path joining
u and v in T.
if the weight
function satisfies the triangle inequality [397].
for all u,v, admits a PTAS [469].