d-dimensional arrangement revisited

• We revisit approximation algorithms for d-dimensional arrangement and point out a mistake in their analyses.
• We prove that the worst-case ratio of linear arrangement with d-dimensional cost to d  -dimensional arrangement is O(logn).
• We conclude that the best known approximation ratio for d  -dimensional arrangement is Θ(logn), for any fixed d⩾2d⩾2.

We revisit the d-dimensional arrangement problem and analyze the performance ratios of previously proposed algorithms based on the linear arrangement problem with d  -dimensional cost. The two problems are related via space-filling curves and recursive balanced bipartitioning. We prove that the worst-case ratio of the optimum solutions of these problems is Θ(logn), where n is the number of vertices of the graph. This invalidates two previously published proofs of approximation ratios for d  -dimensional arrangement. Furthermore, we conclude that the currently best known approximation ratio for this problem is O(logn).