论文标题
关于ULAMS指标在较高的维度和双重相关层次结构中的易干性
On Tractability of Ulams Metric in Highier Dimensions and Dually Related Hierarchies
论文作者
论文摘要
ULAM的度量是从排列中删除一个元素及其随后在不同位置的重新插入的移动数量最少，以在两个给定的排列之间进行。未移动的元素创造了最长的置换子序列。 Aldous和Diaconis在他们的论文中指出，Ulam的指标是在有关分类和抛弃卡的问题的背景下引入的。在本文中，我们在较高的维度上定义和研究ULAM的指标：对于维度一个，所考虑的对象是一对置换，对于尺寸K，它是一对k-tupers of Permudations。通过k-tupers的编码，我们定义了两个双重相关的层次结构。我们的第一个动机来自Al的Murata。纸张，将成对的排列用作用作最小区域的矩形之间的拓扑关系，并应用于VLSI物理设计。我们的结果涉及层次结构内部的硬度，近似性和参数化的复杂性。
The Ulam's metric is the minimal number of moves consisting in removal of one element from a permutation and its subsequent reinsertion in different place, to go between two given permutations. Thet elements that are not moved create longest common subsequence of permutations. Aldous and Diaconis, in their paper, pointed that Ulam's metric had been introduced in the context of questions concerning sorting and tossing cards. In this paper we define and study Ulam's metric in highier dimensions: for dimension one the considered object is a pair of permutations, for dimension k it is a pair of k-tuples of permutations. Over encodings by k-tuples of permutations we define two dually related hierarchies. Our very first motivation come from Murata at al. paper, in which pairs of permutations were used as representation of topological relation between rectangles packed into minimal area with application to VLSI physical design. Our results concern hardness, approximability, and parametrized complexity inside the hierarchies.
