Next: MINIMUM RELEVANT VARIABLES IN
Up: Mathematical Programming
Previous: MINIMUM QUADRATIC 0-1 ASSIGNMENT
  Index
- 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
d(z(c1),z(c2)) is the discretized Euclidean distance between the
points z(c1) and z(c2).
- 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
[278].
Viggo Kann
1999-04-22