کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
428552 | 686810 | 2013 | 8 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: d-dimensional arrangement revisited d-dimensional arrangement revisited](/preview/png/428552.png)
• 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).
Journal: Information Processing Letters - Volume 113, Issue 13, 15 July 2013, Pages 498–505