MINIMUM PLANAR RECORD PACKING

• INSTANCE: Collection C of n records, for each record $c\in C$ a probability p(c) such that $0\le p(c)\le 1$.

• SOLUTION: For each record $c\in C$ a placement z(c) in the plane, given as integer coordinates, such that all records are placed on different points in the plane.

• MEASURE: $$\sum\limits_{c_1\in C} \displaystyle\sum\limits_{c_2\in C} p(c_1) p(c_2) d(z(c_1),z(c_2))$$, where $d(z(c_1),z(c_2))$ is the discretized Euclidean distance between the points $z(c_1)$ and $z(c_2)$.

  
  

• Good News: Approximable with an absolute error guarantee of $\lfloor 4\sqrt{2}+8\sqrt{\pi}\rfloor$, that is, one can in polynomial time find a solution with objective function value at most $\mbox{\sl opt}+\lfloor 4\sqrt{2}+8\sqrt{\pi}\rfloor$ [293].