Random projection: a new approach to VLSI layout
Random projection: a new approach to VLSI layout
复制标题
随机投影：VLSI布局的新方法
DOI：
--
复制
发表时间：
1998
期刊：
影响因子：
--
通讯作者：
S. Vempala
中科院分区：
文献类型：
--
作者：
S. Vempala
我们表明，随机投影，一组点的投影到一个随机选择的低维子空间的技术，可以用来解决问题的VLSI布局。具体来说，对于在二维网格上布置图以最小化最大边长的问题，我们得到了O（log/sup 3.5/ n）的近似算法（这是第一个O（n）近似），对于最小化总边长同时保持最大长度有界的双准则问题，我们得到了O（log/sup 3/ n，log/sup 3.5/ n）的近似。我们的算法也适用于d维版本的这些问题（对于任何固定的d）与polylog近似保证。除了随机投影，算法的主要组成部分是一个线性规划松弛，体积尊重欧几里得嵌入。
We show that random projection, the technique of projecting a set of points to a randomly chosen low-dimensional subspace, can be used to solve problems in VLSI layout. Specifically, for the problem of laying out a graph on a 2-dimensional grid so as to minimize the maximum edge length, we obtain an O(log/sup 3.5/ n) approximation algorithm (this is the first o(n) approximation), and for the bicriteria problem of minimizing the total edge length while keeping the maximum length bounded, we obtain an O(log/sup 3/ n, log/sup 3.5/ n) approximation. Our algorithms also work for d-dimensional versions of these problems (for any fixed d) with polylog approximation guarantees. Besides random projection, the main components of the algorithms are a linear programming relaxation, and volume-respecting Euclidean embeddings.