Next:
MS13 MINIMUM PHYLOGENETIC
Up:
Miscellaneous
Previous:
MS11 SHORTEST PATH
-
I
NSTANCE
:
A set of
n
points in the plane.
-
S
OLUTION
:
A collection of
n
axis-aligned equal-sized squares (labels) such that
(a) every point is the corner of exactly one square, and (b) all squares are
pairwise disjoint.
-
M
EASURE
:
The area of the squares.
-
Good News:
Approximable within 2 [
341
].
-
Bad News:
Non approximable within
for any
[
110
].
-
Comment:
The generalized problem, where equal-sized rectangles or ellipses are allowed
as labels, and where the labels may have any orientation and may have any
point on the boundary at the point in the plane, is in A
PX
. The generalized
problem is approximable within 14 when the labels are squares and within
15 when the labels are circles [
93
].
Viggo Kann
Mon Apr 21 13:07:14 MET DST 1997