Def: M24 consists of all metric spaces such that
All distances are 1 or 2.
d(x,y) + d(x,z) + d(y,z) ≤ 4
Why M24
A step in the direction of the goal (better than 2-competitive randomized algorithm for the 2-server problem).
Allows a simple example of the knowledge state method.
An interesting class in its own right, derived from the cross polytopes, an infinite family of regular convex polytopes, generalizing the octahedron.
|