In the Order-Maintenance Problem, the objective is to maintain a total order subject to insertions, deletions, and precedence queries. Known optimal solutions,
due to Dietz and Sleator, are complicated. We present new algorithms that match the bounds of Dietz and Sleator. Our solutions
are simple, and we present experimental evidence that suggests that they are superior in practice.
Supported in part by NSF Grants CCR-9800085 and CCR-0105678.
Supported in part by NSF Grant EIA-0112849.
Supported in part by NSF Grant CCR-9820879.