Next: MINIMUM RELEVANT VARIABLES IN Up: Mathematical Programming Previous: MINIMUM QUADRATIC 0-1 ASSIGNMENT Index

### MINIMUM PLANAR RECORD PACKING

- 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].