37608950
Efficient Heuristics for Orientation Metric and Euclidean Steiner Tree Problems
AbstractWe consider Steiner minimum trees (SMT) in the plane, where only orientations with angle
$${\sigma }$$
 , 0 ≤ i ≤ σ − 1 and σ an integer, are allowed. The orientations define a metric, called the orientation metric, λσ, in a natural way. In particular, λ2 metric is the rectilinear metric and the Euclidean metric can beregarded as λ∞ metric. In this paper, we provide a method to find an optimal λσ SMT for 3 or 4 points by analyzing the topology of λσ SMT's in great details. Utilizing these results and based on the idea of loop detection first proposed in Chao and Hsu, IEEE Trans. CAD, vol. 13, no. 3, pp. 303–309, 1994, we further develop an O(n2) time heuristic for the general λσ SMT problem, including the Euclidean metric. Experiments performed on publicly available benchmark data for 12 different metrics, plus the Euclidean metric, demonstrate the efficiency of our algorithms and the quality of our results.
47450428
An Algorithm to Compact a VLSI Symbolic Layout with Mixed Constraints
A popular algorithm to compact VLSI symbolic layout is to use a graph algorithm similar to finding the "longest path" in a network. The algorithm assumes that the spacing constraints on the mask elements are of the lower bound type. However, to enable the user to have close control over the compaction result, a desired symbolic layout system should allow the user to add either the equality or the upper bound constraints on selected pairs of mask elements as well. This paper proposes an algorithm which uses a graph-theoretic approach to solve efficiently the compaction problem with mixed constraints.
8508688
New algorithms for the rectilinear Steiner tree problem
An approach to constructing the rectilinear Steiner tree (RST) of a given set of points in the plane, starting from a minimum spanning tree (MST), is discussed. The main idea in this approach is to find layouts for the edges of the MST that maximize the overlaps between the layouts, thus minimizing the cost (i.e. wire length) of the resulting rectilinear Steiner tree. Two algorithms for constructing rectilinear Steiner trees from MSTs, which are optimal under the conditions that the layout of each edge of the MST is an L shape or any staircase, respectively, are described. The first algorithm has linear time complexity and the second algorithm has a higher polynomial time complexity. Steiner trees produced by the second algorithm have a property called stability, which allows the rerouting of any segment of the tree, while maintaining the cost of the tree, and without causing overlaps with the rest of the tree. Stability is a desirable property in VLSI global routing applications. >
31592050
Analysis of a General Mass Storage System
A model of a general mass storage system is presented and its performance analyzed. The system is composed of a square two-dimensional grid of storage cells over which a single read/write head moves freely. The head can contain at most some fixed number b of cell contents. Algorithms for realizing an arbitrary permutation of the memory contents are presented for all ranges of b, particularly the important case $b = 1$; in each case the algorithms’ performances are explicitly characterized. Open problems, especially regarding the development of good heuristics, are then discussed.
21236849
Near-Optimal Solutions to a 2-Dimensional Placement Problem
We consider the problem of placing records in a 2-dimensional storage array so that expected distance between consecutive references is minimized. A simple placement heuristic which uses only relative frequency of access for different records is shown to be within an additive constant of optimal when distance is measured by the Euclidean metric. For the rectilinear and maximum metrics, we show that there is no such heuristic. For the special case in which all access probabilities are equal, however, heuristics within an additive constant of optimal do exist, and their implementation requires solution of differential equations for which we give numerical solutions.
10692185
Optimal and Near-Optimal Scheduling Algorithms for Batched Processing in Linear Storage
In this paper, we consider the accessing of batched requests in a linear storage medium. The batch size is assumed fixed and the access probabilities of individual records known. For a given arrangement of records in the storage, we consider the problem of read/write head scheduling to minimize the expected access time for a batch measured in terms of the distance traveled by the head. In the first part of the paper, several simple algorithms are proposed, analyzed and compared. The effect of different record arrangements is also discussed. In the second part of the paper, a family of algorithms called B-optimal rules are described. When B is $\infty $, an $\infty $-optimal rule is indeed optimal in the sense of minimizing expected distance traveled by the head per batch when accessing an arbitrarily large number of batches. A procedure to calculate an $\infty $-optimal rule for any given record arrangement is described, which is based on the idea of “discrete dynamic programming”.
30930498
Chinese document indexing based on a new partitioned signature file: Model and evaluation
In this article we investigate the use of signature files in Chinese information retrieval system and propose a new partitioning method for Chinese signature file based on the characteristic of Chinese words. Our partitioning method, called Partitioned Signature File for Chinese (PSFC), offers faster search efficiency than the traditional single signature file approach. We devise a general scheme for controlling the trade-off between the false drop and storage overhead while maintaining the search space reduction in PSFC. An analytical study is presented to support the claims of our method. We also propose two new hashing methods for Chinese signature files so that the signature file will be more suitable for dynamic environment while the retrieval performance is maintained. Furthermore, we have implemented PSFC and the new hashing methods, and we evaluated them using a large-scale real-world Chinese document corpus, namely, the TREC-5 (Text REtrieval Conference) Chinese collection. The experimental results confirm the features of PSFC and demonstrate its superiority over the traditional single signature file method.
8828112
Real-Time Rate Control Via Variable Frame Rate and Quantization Parameters
Most of existing rate control schemes in the literature focus on the bit allocation under the assumption of constant frame rate. As a result, the distortion of consecutive frames varies in a great extent, which may result in low temporal quality (e.g. flickering effect). In this work, we design rate control with two control parameters (i.e. quantization factor and frame rate) to achieve better tradeoff between spatial quality and temporal quality in low complexity. Our optimization gives two suggested quantization step sizes. One is used to change the frame rate in order to allocate how many bits used in the current frame. Another one is used to change the quantization factor in order to quantize MBs to achieve target bit rates. The experimental results suggest that our scheme can achieve more consistent quality while keeping high spatial quality.
195859283
On fixed edges and edge-reconstruction of series-parallel networks
A graph configuration is a vertex labeled simple graph. We say a configuration is exclusive for graphs with a property in a class of graphs if every graph in the class containing the configuration has the property. We use the method of exclusive configurations to search for graphs without fixed edges and forced edges investigate the fixed edges. An edge e of a graph G is said to be a fixed edge if G-e+e'/spl cong/G implies that e'=e, and a forced edge if G-e+e' is an edge-reconstruction of G implies that e'=e. It is proved that all series-parallel networks contain fixed edges and forced edge except P/sub 2//spl times/K/sub 1/ and P/sub 3//spl times/K/sub 1/. A similar method is used to investigate the alternative wire problem in circuit design. Let G be a Boolean network and w a wire in G. Wire w' is said to be an alternative wire of w if w'/spl ne/w and G-w+w' has the same functionality as that of G. A wire is said to be fixed if it has no alternative wire. We present a set of exclusive configurations for Boolean networks in which every wire is fixed.
16381803
Upper and lower bounds for graph-diameter problems with application to record allocation
This paper studies three graph problems with parameters n, the number of nodes, e, the number of edges, and k, the diameter of the graph. Given any two of these three parameters, the problem is to construct a directed graph which minimizes or maximizes the third. The first problem has its origin in a recent study of record allocation in a paged computer system. It is shown how to construct graphs that are optimal for all three problems in some cases and are asymptotically optimal for other cases. The solution of the second problem answers a question raised by Berge in “The Theory of Graphs and its Application,” 1962.
7180182
Minimizing mean flow time with error constraint
In a new model of task systems studied by J.W.S. Liu et al. (1987) each task is logically decomposed into two subtasks, mandatory and optional. The authors discuss preemptively scheduling this kind of task system on p>or=1 identical processors so as to minimize the mean flow time. Given a task system and an error threshold K, the goal is to find a preemptive schedule such that each task is executed in the interval of its release time and deadline, the average error is no more than K, and the mean flow time of the schedule is minimized. Such a schedule is called an optimal schedule. It is shown that the problem of finding an optimal schedule is NP-hard for each p>or=1, even if all tasks have the same ready time and deadline. For a single processor, a pseudo-polynomial time algorithm and polynomial time algorithms for various special cases of the problem are given.<<ETX>>