Bad News:
Not approximable within 2
for any
[
311
].
Comment:
Not in A
PX
if the distances do not satisfy the triangle inequality.
Maximum Edge Subgraph
is the variation where the measure is the average
distance between any pair of facilities [
311
].
Variation in which we allow the points in
F
to lie in edges (considered as
curves) is also approximable within 2 and is not approximable within
[
329
].
and distances
satisfying the triangle inequality.
with
|F|=k
.
.
for any
[
311
].
[
329
].