d-dimensional arrangement revisited

Autor:	Daniel Rotter, Jens Vygen
Rok vydání:	2013
Předmět:	Combinatorics Discrete mathematics Signal Processing Graph partition Graph (abstract data type) Approximation algorithm Space-filling curve Mathematical proof Computer Science Applications Information Systems Theoretical Computer Science Mathematics
Zdroj:	Information Processing Letters. 113:498-505
ISSN:	0020-0190
DOI:	10.1016/j.ipl.2013.04.003
Popis:	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 @Q(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).
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::3a92c7afa7678ef7826ddbb58406ab4b https://doi.org/10.1016/j.ipl.2013.04.003 Zobrazit plný text záznamu Full Text from ScienceDirect