l22 spreading metrics for vertex ordering problems
l22 spreading metrics for vertex ordering problems
复制标题
用于顶点排序问题的 l22 扩展度量
DOI：
--
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
Satish Rao
中科院分区：
文献类型：
--
作者：
M. Charikar;M. Hajiaghayi;H. Karloff;Satish Rao
我们为顶点排序问题“最小线性排列”、“最小包含间隔图”和“最小存储时间积”设计了近似算法，实现了近似因子 <i>O</i>√log <i>n</i> log log <i>n</i>)、<i>O</i>√log <i>n</i> log log <i>n</i>)，以及<i>O</i>√log <i>T</i> log log <i>T</i>)，分别是 <i>T</i> 中最后一次运行的时间多项式（<i>T</i> 是执行时间的总和）。我们论文的技术贡献是引入 <i>l</i><sup>2</sup><inf>2</inf> 扩展度量”（可以通过半定规划计算）作为无向和有向“排列度量”的松弛，这些排列度量是由 {1, 2, . . ., <i>n</i>} 的排列引起的。Arora、Rao 和 Vazirani 最近的工作中引入的技术可以进行改编利用这种 <i>l</i><sup>2</sup><inf>2</inf> 扩展度量的几何结构，为分而治之算法的设计提供了强大的工具。 除了在近似算法中的应用之外，将这种 <i>l</i><sup>2</sup><inf>2</inf> 扩展度量作为排列度量的松弛进行研究本身就很有趣。从某种意义上说，我们精确地说，<i>l</i><sup>2</sup><inf>2</inf> 分布度量近似于 <i>n</i> 上的排列度量，指向因子 <i>O</i>√log <i>n</i> log log <i>n</i>）。
We design approximation algorithms for the vertex ordering problems MINIMUM LINEAR ARRANGEMENT, MINIMUM CONTAINING INTERVAL GRAPH, and MINIMUM STORAGE-TIME PRODUCT, achieving approximation factors of <i>O</i>√log <i>n</i> log log <i>n</i>), <i>O</i>√log <i>n</i> log log <i>n</i>), and <i>O</i>√log <i>T</i> log log <i>T</i>), respectively, the last running in time polynomial in <i>T</i> (<i>T</i> being the sum of execution times). The technical contribution of our paper is to introduce <i>l</i><sup>2</sup><inf>2</inf> spreading metrics" (that can be computed by semidefinite programming) as relaxations for both undirected and directed "permutation metrics," which are induced by permutations of {1, 2, . . ., <i>n</i>}. The techniques introduced in the recent work of Arora, Rao and Vazirani can be adapted to exploit the geometry of such <i>l</i><sup>2</sup><inf>2</inf> spreading metrics, giving a powerful tool for the design of divide-and-conquer algorithms. In addition to their applications to approximation algorithms, the study of such <i>l</i><sup>2</sup><inf>2</inf> spreading metrics as relaxations of permutation metrics is interesting in its own right. We show how our results imply that, in a certain sense we make precise, <i>l</i><sup>2</sup><inf>2</inf> spreading metrics approximate permutation metrics on <i>n</i> points to a factor of <i>O</i>√log <i>n</i> log log <i>n</i>).