Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
428552 | Information Processing Letters | 2013 | 8 Pages |
•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).