INSTANCE:
Collection C of n records, for each record
a probability
p(c) such that
.
SOLUTION:
For each record
a placement z(c) in the plane, given as integer
coordinates, such that all records are placed on different points in the plane.
MEASURE:
,
where
is the discretized Euclidean distance between the
points
and .
Good News:
Approximable with an absolute error guarantee of
,
that is, one can in polynomial time
find a solution with objective function value at most
[293].