Machine Learned Ranking approaches have shown successes in web search engines. With the increasing demands on developing effective ranking functions for different search domains, we have seen a big bottleneck, i.e., the problem of insufficient training data, which has significantly limited the fast development and deployment of machine learned ranking functions for different web search domains. In this paper, we propose a new approach called tree based ranking function adaptation ("tree adaptation") to address this problem. Tree adaptation assumes that ranking functions are trained with regression-tree based modeling methods, such as Gradient Boosting Trees. It takes such a ranking function from one domain and tunes its tree-based structure with a small amount of training data from the target domain. The unique features include (1) it can automatically identify the part of model that needs adjustment for the new domain, (2) it can appropriately weight training examples considering both local and global distributions. Experiments are performed to show that tree adaptation can provide better-quality ranking functions for a new domain, compared to other modeling methods.

An improved FPGA implementation of an electronic cochlea filter is presented. We show that by using decimation, the computations of the electronic cochlea can be reduced. Furthermore, employing dual fixed-point arithmetic, gives a significant improvement in signal to noise ratio. A sequential architecture is described which employs pipelined infinite impulse response filter stages. The accuracy, performance and resource utilisation of a number of different implementations are compared.

A single chip FPGA-based Othello endgame solver is presented in This work. The solver includes all the hardware for move checking, disc flipping, move selection, board evaluation and alpha-beta pruning. On a Xilinx Virtex XCVW00E-6 device operating at 50 MHz, the chip can search 3.14 million Othello positions per second. The endgame chip achieves a speedup of 3.5 over an 800 MHz Pentium III machine, showing that performance similar to that of a high end microprocessor can be achieved using modest FPGA resources. By using a larger FPGA, a more sophisticated search algorithm and an improved datapath, we believe that a single FPGA based endgame solver with at least two orders of magnitude better performance can be developed.

Switch modules are the most important component of the routing resources in FPGAs/FPICs. Previous works have shown that switch modules with higher routability result in better area performance for practical applications. We consider in this paper an FPGA/FPIC switch-module analysis problem: the inputs consist of a switch-module description and the number of nets required to be routed through the switch module; the question is to determine if there exists a feasible routing for the routing requirements on the switch module. As a fundamental problem for the analysis of switch modules, this problem is applicable to the design and routability evaluation of FPGA/FPIC switch modules and FPGA/FPIC routing. We present a network-flow-based approximation algorithm for this problem. Based on mathematical analyses, we show that this algorithm has provably good performance with the bounds 5 and 5/4 away from the optima for two types of switch modules, respectively. Extensive experiments show that this algorithm is highly accurate and runs very efficiently.

A k -side switch block with W terminals per side is said to be a universal switch block (( k , W )-USB) if every set of the nets satisfying the routing constraint (i.e., the number of nets on each side is at most W ) is simultaneously routable through the switch block. The (4, W )-USB was originated by designing better switch modules for 2-D FPGAs, such as Xilinx XC4000-type FPGAs, whereas the generic USBs can be applied in multidimensional or some nonconventional 2-D FPGA architectures. The problem we study in this article is to design ( k , W )-USBs with the minimum number of switches for any given pair of ( k , W ). We provide graph models for routing requirements and switch blocks and develop a series of decomposition theorems for routing requirements with the help of a new graph model. The powerful decomposition theory leads to the automatic generation of routing requirements and a detailed routing algorithm, as well as the reduction design method of building large USBs by smaller ones. As a result, we derive a class of well-structured and highly scalable optimum ( k , W )-USBs for k ≤ 6, or even W s, and near-optimum ( k , W )-USBs for k ≥ 7 and odd W s. We also give routing experiments to justify the routing improvement upon the entire chip using the USBs. The results demonstrate the usefulness of USBs.

In this paper, we study the propagation of slew dependent bounding signals and the corresponding slew problem in static timing analysis. The selection of slew from the latest arriving signal, a commonly used strategy, may violate the rule of monotonic delay. Several methods for generating bounding signals to overcome this difficulty are described. The accuracy and monotonicity of each method is analyzed. These methods can be easily implemented in a static timer to improve the accuracy.

There have been various algorithms designed for simulating natural evolution. This paper proposes a new simulated evolutionary computation model called the abstract evolutionary algorithm (AEA), which unifies most of the currently known evolutionary algorithms and describes the evolution as an abstract stochastic process composed of two fundamental operators: selection and evolution operators. By axiomatically characterizing the properties of the fundamental selection and evolution operators, several general convergence theorems and convergence rate estimations for the AEA are established. The established theorems are applied to a series of known evolutionary algorithms, directly fielding new convergence conditions and convergence rate estimations of various specific genetic algorithms and evolutionary strategies. The present work provides a significant step toward the establishment of a unified theory of simulated evolutionary computation.

In this paper, we analyze the basic properties of some Boolean function classes and propose a low complexity OBDD variable ordering algorithm, which is exact (optimum) to some classes of functions and very effective to general two-level form functions. We show that the class of series-parallel functions, which can be expressed by a factored form where each variable appears exactly once, can yield exact OBDD variable orderings in polynomial time. We also study the thin Boolean functions whose corresponding OBDDs can be represented by the form of thin OBDDs in which the number of nonterminal nodes is equal to the number of input variables. We show,that a thin Boolean function always has an essential prime cube cover and the class of series-parallel functions is a proper subset of thin Boolean functions. We propose a heuristic viewing OBDDs as evaluation machines with function cube covers as their inputs and apply a queuing principle in the algorithm design. Our heuristic, the augmented Dynamic Shortest Cube First algorithm, is proven to be optimum for the series-parallel functions and also be very effective for general two-level form functions. Experimental results on a large number of two-level form benchmark circuits show that the algorithm yields an OBDD total size reduction of over 51 percent with only 7 percent CPU time compared to the well-known network-based Fan-in Heuristic implemented in the SIS package. Comparing to the known exact results, ours is only 49 percent larger in size while only uses 0.001 percent CPU time.

Simulated annealing is a robust and easy-to-implement algorithm for material simulation. However, it consumes a huge amount of computational time, especially on the studies of percolation networks. To reduce the running time, we parallelize the simulated annealing algorithm in our studies of the thermoelastic scaling behavior of percolation networks. The critical properties of the thermoelastic moduli of percolation networks near the threshold p/sub c/ are investigated by constructing a square percolation network. The properties are tested by simulations of a series of two-dimensional (2-D) percolation networks near p/sub c/. The simulations are performed using a novel parallelizing scheme on the simulated annealing algorithm. To further accelerate the computational speed, we also propose a new conjectural method to generate better initial configurations, which speeds up the simulation significantly. Preliminary simulation results show surprisingly that the percolating phenomenon of thermal expansion does exist under certain conditions. The behavior seems to be governed by the elastic properties of a percolation network.

For the FPGA Greedy Routing Architectures (GRAs), the optimal mapping problem of the entire chip can be decomposed into a sequence of three kinds of optimal m-side predetermined 4-way FPGA mapping problems, where m could be 1, 2, or 3. In this paper, we formulate the graph models of such sub-routing problems and investigate their minimum structures. The results give the lower bounds of routing resources in achieving all such kinds of GRAs and the theoretic models developed could be useful to studies on other FPGA routing problems as well.

This paper investigates the optimum OBDD representation problem based on two classes of Boolean functions. The first class is defined by OBDDs, in which the number of non-terminal nodes is equal to the number of input variables. We refer to such OBDDs and their corresponding Boolean functions as thin OBDDs and thin Boolean functions. The second class is the thin factored Boolean functions, which is defined by factored forms with each variable appearing exactly once. Many interesting properties of these two classes of functions are presented. Based on which, a revised dynamic shortest cube first OBDD variable ordering algorithm is developed. This algorithm is shown to be optimum for thin factored Boolean functions.

We study the reproducing placement problem, which finds application in layout-driven logic synthesis. In each phase, a module (or gate) is decomposed into two (or more) simpler modules. The goal is to find a "good" placement in each phase. The problem, being iterative in nature, requires an iterative algorithm. In solving the RPP, we introduce the notion of minimum floating Steiner trees (MFST). We employ an MFST algorithm as a central step in solving the RPP. A Hanan-like theorem is established for the MFST problem, and two approximation algorithms are proposed. Experiments on commonly employed benchmarks verify the effectiveness of the proposed technique.

We describe some numerical techniques for the total variation image restoration method, namely a primal-dual linearization for the Euler-Lagrange equations and some preconditioning issues. We also highlight extension of this technique to color images, blind deconvolution and the staircasing effect.

We study a new version of the shortest path problem. Let G = (V, E) be a directed graph. Each are e ∈ E has two numbers attached to it: a transit time b(e, u) and a cost c(e, u), which are functions of the departure time u at the beginning vertex of the arc. Moreover, postponement of departure (i.e., waiting) at a vertex may be allowed. The problem is to find the shortest path, i.e., the path with the least possible cost, subject to the constraint that the total traverse time is at most some number T. Three variants of the problem are examined. In the first one, we assume arbitrary waiting times, where waiting at a vertex without any restriction is allowed. In the second variant, we assume zero waiting times, namely, waiting at any vertex is strictly prohibited. Finally, we consider the general case whre there is a vertex-dependent upper bound on the waiting time at each vertex. Several algorithms with pseudopolynomial time complexity are proposed to optimally solve the problems. First, we assume that all transit times b(e, u) are positive integers. In the last section, we show how to include zero transit times. © 1997 John Wiley & Sons, Inc. Networks 29: 141–149, 1997

The authors consider optimal placements of two-dimensional flexible (elastic, deformable) objects. The objects are discs of equal size placed within a rigid boundary. The paper is divided into two parts. In the first part, analytical results for three types of regular, periodic arrangements-the hexagonal, square, and triangular placements-are presented. The regular arrangements are analyzed for rectangular boundaries and radii of discs that are small compared to the area of the placement region, because, in this case, the influence of boundary conditions can be neglected. This situation is called the unbounded case. They show that, for the unbounded case among the three regular placements, the type of hexagonal arrangements provides the largest number of placed units for the same deformation depth. Furthermore, it can be proved that these regular placements are not too far from the truly optimal arrangements. For example, hexagonal placements differ at most by the factor of 1.1 from the largest possible number of generally shaped units in arbitrary arrangements. These analytical results are used as guidances for testing stochastic algorithms optimizing placements of flexible objects. In the second part, mainly two problems are considered: the underlying physical model and a simulated annealing algorithm maximizing the number of flexible discs in equilibrium placements. Along with the physical model, an approximate formula is derived, reflecting the deformation/force relationship for a large range of deformations.

For pt.I see ibid., p.890-904. The paper is a continuation of the first part, where the authors considered regular arrangements of flexible objects for the unbounded case. The present part deals with a simulated annealing algorithm maximizing the number of flexible objects in equilibrium placements within rigid boundaries. The forces caused by the boundary are taken into account, i.e., the bounded case of placements is considered. The simulated annealing procedure makes use of the special structure of the underlying configuration space and relationships between deformations of flexible objects and resulting forces. This allows one to obtain tight bounds for the annealing parameters which result in n/sup 3/2//spl middot/In/sup 5/2/ and n/spl middot/In/sup 2/n time bounds, respectively, for the computation of equilibrium states by two different cooling schedules. The deformation/force formula is derived from a physical model of flexible discs and is based on numerical experiments which were performed for different materials and different sizes of objects. The algorithm was first implemented and tested for the unbounded case. The run-time is relatively short, even for large numbers of placed discs. These results are compared to the analytical ones obtained for regular placements in the first part of the paper, and agreement between these two sets of results are observed. Furthermore, several experiments for placements with boundary conditions were carried out and the resulting placements clearly show the effect of the forces from the rigid boundary.

Smallest rectilinear paths are rectilinear paths with simultaneous minimum numbers of bends and minimum lengths. Given two pairs of terminals within a rectilinear polygon, the authors derive an algorithm to find a pair of noncrossing rectilinear paths within the polygon such that the total number of bends and the total length are both minimized. Although a smallest rectilinear path between two terminals in a rectilinear polygon always exists, they show that such a smallest pair may not exist for some problem instances. In that case, the algorithm presented will find, among all noncrossing paths with a minimum total number of bends, a pair whose total length is the shortest, or find, among all noncrossing paths with a minimum total length, a pair whose total number of bends is minimized. They provide a simple linear time and space algorithm based on the fact that there are only a limited number of configurations of such a solution pair.

A new class of routing structures with fixed orthogonal wire segments and field programmable switches at the intersections of the wire segments is proposed. In comparison with the conventional two-dimensional field-programmable gate array (FPGA) routing structure, this class of routing structures has the advantage of using a smaller number of active programmable switches. An existing field-programmable interconnect chip (FPIC) routing structure can be included as a special case in our class of routing structures. Using a probabilistic model, we prove that complete routing can be achieved with a high degree of probability in a routing structure of this class in which the number of tracks in each channel approaches the lower bound asymptotically. We present a sequential routing algorithm based on the solution of the single net routing problem. We take into account the delay introduced by the active programmable switches on a routing path and formulate the single net routing problem as a node-weighted Steiner minimum tree (NWSMT) problem in a bipartite graph G. Since our single net routing problem is NP-complete, a polynomial time approximate algorithm is proposed. We prove that our single net routing algorithm produces an optimal solution for some special classes of bipartite graphs. In general, the solution obtained by our algorithm bas a performance bound of min{/spl Delta/(V/Z), |Z|-1}. Experimental results for several industrial circuits show a reduction of up to 41% in the number of active programmable switches when compared with corresponding results for the conventional FPGA routing structure.

No abstract available.

For a logic design with level-sensitive latches, we need to validate timing signal paths which may flush through several latches. We developed efficient algorithms based on the modified shortest and longest path method. The computational complexity of our algorithm is generally better than that of known algorithms in the literature. The implementation (CYCLOPSS) has been applied to an industrial chip to verify the clock schedules.

A switch module M with W terminals on each side is said to be universal if every set of nets satisfying the dimensional constraint (i.e., the number of nets on each side of M is at most W ) is simultaneously rout able through M . In this article, we present a class of universal switch modules. Each of our switch modules has 6 W switches and switch-module flexibility three (i.e, F s =3). We prove that no switch module with less than 6 W switches can be universal. We also compare our switch modules with those used in the Xilinx XC4000 family FPGAs and the antisymmetric switch modules (with F S =3) suggested by Rose and Brown [1991]. Although these two kinds of switch modules also have F S =3 and 6 W switches, we show that they are not universal. Based on combinatorial counting techniques, we show that each of our universal switch modules can accommodate up to 25% more routing instances, compared with the XC4000-type switch module of the same size. Experimental results demonstrate that our universal switch modules improve routability at the chip level. Finally, our work also provides a theoretical insight into the important observation by Rose and Brown [1991] (based on extensive experiments) that F S =3 is often sufficient to provide high routability.

Unlike traditional ASIC routing, the feasibility of routing in FPGAs is constrained not only by the available space within a routing region, but also by the routing capacity of a switch block. Recent work has established the switch-block capacity as a superior congestion-control metric for FPGA global routing. However, the work has two deficiencies: (1) its algorithm for computing the switch-block capacity is not efficient, and (2) it, as well as the other recent works only modeled one type of routing segments-single-length lines. To remedy the deficiencies, we present in this paper efficient algorithms for obtaining the switch-block capacity and a graph modeling for routing on the new generation FPGAs with a versatile set of segment lengths. Experiments show that our algorithms dramatically reduce the run times for obtaining the switch-block capacities. Experiments with a global router based on the switch-block and channel densities for congestion control show a significant improvement in the area performance, compared with one based on the traditional congestion metric.

Switch modules are the most important component of the routing resources in FPGAs and FPICs. The quality of switch modules greatly affects FPGA/FPIC routing solutions. The switch-module design problem was studied by K. Zhu et al. (1993). In order to analyze the routability of designed switch modules, a heuristic algorithm based on network-flow techniques was proposed. In this paper, we mathematically show that the network-flow based algorithm has provably good performance with the bounds 5 and 5/4 away from the optima for two types of switch modules, respectively. Based on the analyses, we developed a new method for designing switch modules. Experimental results show that our designed switch modules significantly improve routability, compared with those by K. Zhu et al. Extensive experiments also show that the network-flow based algorithm is highly accurate and runs very efficiently.

Efficient algorithms are presented for finding rectilinear collision-free paths between two given points among a set of rectilinear obstacles. The results improve the time complexity of previous results for finding the shortest rectilinear path the minimum-bend shortest rectilinear path, the shortest minimum-bend rectilinear path and the minimum-cost rectilinear path. For finding the shortest rectilinear path, a graph-theoretic approach is used and an algorithm is obtained with $O(m \log t + t \log^{3/2}t)$ running time, where t is the number of extreme edges of given obstacles and m is the number of obstacle edges. Based on this result an $O(N \log N + (m + N) \log t + (t+N) \log^{2} (t + N))$ running time algorithm for computing the $L_{1}$ minimum spanning tree of given N terminals among rectilinear obstacles is obtained. For finding the minimum-bend shortest path, the shortest minimum-bend rectilinear path, and the minimum-cost rectilinear path, we devise a new dynamic-searching approach and derive algorithms that run in $O(m \log^{2} m)$ time using $O(m \log m)$ space or run in $O(m \log^{3/2} m)$ time and space.

We study in this paper the net assignment problem subject to the capacity constraint, selection constraint and routing constraint. Given two adjacent channels separated by a cell row, and a set of nets in each of the two channels, this problem is to assign to the cell row a subset of nets in each channel such that without violating any given constraint, the sum of the remaining densities of the two channels is minimized. The capacity constraint requires the density caused by the nets, which are assigned to the cell row, to be no more than a user-specified number k, where k is no more than the number of tracks available for routing over that cell row. The selection constraint specifies in each channel the subset of nets which are candidates to be assigned to the cell row. The routing constraint requires each net to be either completely assigned to the cell row or to stay in its channel. This problem can find its application in modeling a practical over-the-cell routing problem in which the whole region over the cell row is two-layer routable for the nets in the two adjacent channels. We present an optimal algorithm to solve this problem and provide experimental results to support our algorithm.

We consider problems of finding assorted rectilinear paths among rectilinear obstacles in a two-layer interconnection model according to the number of bends and the 1-layer distance (y-distance). Using a horizontal wave-front approach, optimal /spl theta/(e log e) time algorithms are presented to find the shortest path and the minimum-bend path using linear space, and to find the shortest minimum-bend path and the minimum-bend shortest path using O(e log e) space, where e is the number of obstacle edges. By the same approach, we also derive an algorithm for finding a shortest two-layer distance (xy-distance) minimum-bend path in optimal /spl theta/(e log e) time using O(e log e) space.>

We consider the problem of global routing, aiming to simultaneously minimize wire length and density through the regions. Previous global routers have attempted to achieve this goal; however, they minimized one of the two parameters as the main objective and proposed heuristics for minimizing the other parameter. We accomplish this task by introducing the concept of weighted Steiner trees. We propose an efficient and simple algorithm for obtaining a weighted (rectilinear) Steiner tree in the plane. The proposed global router at each step finds a weighted Steiner tree for a net, where weight of a region represents its "complexity". Weights of the regions are dynamically changing. Experimental results on master slice chips and on benchmark examples from the Physical Design Workshop are included, and they verify the effectiveness of the proposed global router and its superiority over related global routers.>

We introduce the single-layer global routing problem (SLGRP), also called homotopic routing or rubber-band-equivalent routing, and propose a technique for solving it. Given a set of nets, the proposed technique first determines the routing sequence based on the estimated congestion, the bounding-box length and priority. Then, it finds a routing path, being a sequence of tiles, for each net (one net at a time), avoiding "congested" areas. The overall goal of the algorithm is to maximize the number of routed nets. The proposed global router is the first true single-layer global router ever reported in the literature. The size of tiles, w/spl times/w, is an input parameter in our algorithm. For w=1, the proposed global router serves as an effective detailed router. An optimal postprocessing algorithm, minimizing wire length and number of bends, under homotopic transformation, is presented. The technique has been implemented and tried out for randomly generated data. The algorithm is very efficient and produces good results.>

A new class of routing structures with fixed orthogonal wire segments and field programmable switches at the intersections of the wire segments is proposed. In comparison with the conventional two dimensional field-programmable gate array (FPGA) routing structure, this class of routing structures has the advantage of using a smaller number of programmable switches. Using a probabilistic model, we prove that complete routing can be achieved with a high degree of probability in a routing structure of this class in which the number of tracks in each channel approaches the lower bound asymptotically. A sequential routing algorithm which is based on the solution of the single net routing problem is presented. We take into account the delay introduced by the programmable switches on a routing path and formulate the single net routing problem as a Node-Weighted Steiner Minimum Tree (NWSMT) problem in a bipartite graph G. Since our single net routing algorithm is proposed. We prove that our single net routing algorithm produces an optimal solution for some special classes of bipartite graphs. In general, the solution obtained by our algorithm has a performance bound of min{/spl Delta/(VZ), |Z|-1}. On the other hand, we also prove that it is NP-complete to determine a solution which approximates the optimal solution without any constant bound. Experimental results show a reduction of up to 41% in the number of programmable switches when compared with corresponding results for the conventional FPGA routing structure.

A Steiner tree with maximum-weight edge minimized is called a bottleneck Steiner tree (BST). The authors propose a Theta ( mod rho mod log mod rho mod ) time algorithm for constructing a BST on a point set rho , with points labeled as Steiner or demand; a lower bound, in the linear decision tree model, is also established. It is shown that if it is desired to minimize further the number of used Steiner points, then the problem becomes NP-complete. It is shown that when locations of Steiner points are not fixed the problem remains NP-complete; however, if the topology of the final tree is given, then the problem can be solved in Theta ( mod rho mod log mod rho mod ) time. The BST problem can be used, for example, in VLSI layout, communication network design, and (facility) location problems.>

The authors propose a provably good performance-driven global routing algorithm for both cell-based and building-block design. The approach is based on a new bounded-radius minimum routing tree formulation. The authors first present several heuristics with good performance, based on an analog of Prim's minimum spanning tree construction. Next, they give an algorithm which simultaneously minimizes both routing cost and the longest interconnection path, so that both are bounded by small constant factors away from optimal. They also show that geometry helps in routing: in the Manhattan plane, the total wire length for Steiner routing improves to 3/2*(1+(1/ epsilon )) times the optimal Steiner tree cost, while in the Euclidean plane, the total cost is further reduced to (2/ square root 3)*(1+(1/ epsilon )) times optimal. The method generalizes to the case where varying wire length bounds are prescribed for different source-sink paths. Extensive simulations confirm that this approach works well.>

To develop an efficient cell compactor for practical use, the authors take the one-dimensional compaction approach, but with a mixed symbolic and shape data model. A new algorithm of automatic jog generation is employed to create jogs, not only on critical paths but also on some noncritical paths. An optimum wire length minimization algorithm is used to tighten wires and polygon edges. These algorithms help reduce both the cell size and the parasitic, and hence produce high-quality layouts. The compactor has been used at IBM in the production of several standard cell libraries and macrocells,.>

A hierarchical approach to Steiner tree construction in lambda -geometry is proposed. The algorithm runs in time O(n log n) and the length of the constructed tree is at most ( sigma /cos( pi /2 lambda )) times (for lambda =2, 3/2 times) the length of the optimal Steiner tree where n is the cardinality of the point set and it was recently proved that sigma is (2/ square root 3). How to trade off between the running time of the algorithm and the length of the produced Steiner tree is shown. Given enough time, an optimal Steiner tree will be obtained. The algorithm is extended to construct a Steiner tree of a set of subtrees (i.e., partial trees) and runs in O( lambda N log N) time, where N is the total number of edges of the subtrees.>

Advances in VLSI technology and the increased complexity of circuit designs cause performance to become an increasingly important constraint for layout. The issue of delay optimization during the global routing phase is addressed. This problem is formulated as the construction of a bounded-radius spanning tree for a given pointset in the plane, and a family of effective heuristics is presented. This approach has very good empirical performance with respect to total wirelength, and can be smoothly tuned between the competing requirements of minimum delay and minimum total netlength, as confirmed by extensive computational results which confirm this. Extensions can be made to the graph and Steiner versions of the problem, and a number of open problems are described.>

The problem of finding a minimum diameter spanning tree (MDST) of a set of n points in the Euclidean space is considered. The diameter of a spanning tree is the maximum distance between any two points in the tree. A characterization of an MDST is given and a $\theta (n^3)$-time algorithm for solving the problem is presented. The authors also show that for a weighted undirected graph, the problem of determining if a spanning tree with total weight and diameter upper bounded, respectively, by two given parameters C and D exists is NP-complete. The geometric Steiner minimum diameter spanning tree problem, in which new points are allowed to be part of the spanning tree, is shown to be solvable in $O(n)$ time.

The heterogeneous traffic in this environment can be categorized into a rapidly changing type composed of packet switched data traffic and a relatively static type composed of circuit switched voice traffic. From the time-slot assignment viewpoint, the problem is to construct an efficient TDMA frame that permits the static voice traffic to be transmitted and, then, on a frame-by-frame basis to attempt to insert the data packets into the slots that are unused by the voice traffic. It is proved that the problem is NP-complete, even for very simple traffic configurations. Several suboptimal fast heuristic algorithms are presented and empirically compared by experiments on randomly generated traffic patterns. The experiments reveal that, on the average, the algorithms give close to the optimal performance.>

Global routing of multiterminal nets is studied. A novel global router is proposed; each step consists of finding a tree, called a Steiner min-max tree, that is Steiner tree with maximum-weight edge minimized (real vertices represent channels containing terminals of a net, Steiner vertices represent intermediate channels, and weights correspond to densities). An O (min(e loglog e, n/sup 2/)) time algorithm is proposed for obtaining a Steiner min-max tree in a weighted graph with e edges and n vertices. (This result should be contrasted with the NP-completeness of the traditional minimum-length Steiner tree problem). Experimental results on difficult examples, on randomly generated data, on master slice chips, and on benchmark examples from the Physical Design Workshop are included.>

The problem of minimizing the number of power pads, in order to guarantee the existence of a planar routing of multiple power nets, is discussed. A general lower bound is derived, and a heuristic for the general problem is discussed. Several important special cases, including the case of three power nets, are examined, and optimal strategies for pad placement are presented. It is also shown that the general pad minimization problem is NP-complete.>

The layer assignment problem that arises in the design of a multichip module, a high-performance compact package for the interconnection of several hundred chips, is studied. The aim is to place each net in a x-y pair of layers, so as to minimize the number of such pairs. An approximation algorithm, running in O(nd) time is presented for minimizing the number of layers, where n is the number of nets and d is the (two-dimensional) density of the 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.>

We discuss a new approach to constructing the rectilinear Steiner tree (RST) of a given set of points in the plane, starting from a minimum spanning tree (MST). The main idea in our approach is to determine L-shaped layouts for the edges of the MST, so as to maximize the overlaps between the layouts, thus minimizing the cost (i.e., wire length) of the resulting RST. We describe a linear time algorithm for constructing a RST from a MST, such that the RST is optimal under the restriction that the layout of each edge of the MST is an L-shape. The RST's produced by this algorithm have 8-33% lower cost than the MST, with the average cost improvement, over a large number of random point sets, being about 9%. The running time of the algorithm on an IBM 3090 processor is under 0.01 seconds for point sets with cardinality 10. We also discuss a property of RST's called stability under rerouting, and show how to stabilize the RST's derived from our approach. Stability is a desirable property in VLSI global routing applications.

A study is made of the global routing of multiterminal nets. The authors propose a novel global router. Each step consists of finding a tree, called Steiner min-max tree, that is, a Steiner tree with the maximum-weight edge minimized (real vertices represent channels containing terminals of a net, Steiner vertices represent intermediate channels, and weights correspond to densities). An efficient algorithm is presented for obtaining a Steiner min-max tree, in a weighted graph. Experimental results on difficult examples, randomly generated data, master slice chips, and benchmark examples from the physical design workshop are very promising. (In all cases, previous results have been improved.).>

A polynomial time algorithm is given for constructing the minimum cost rectilinear Steiner tree (RST) that is derivable from a minimum spanning tree (MST) of a given point set, such that the MST edges have staircase layouts in the RST. RSTs produced by the algorithm have a property called stability, which enables the rerouting of any subset of the RST edges, while maintaining the cost of the RST, and not causing overlaps with each other or with the other RST edges.>

A description is given of the VHV-channel-routing problem in irregular channels. The authors describe a branch-and-bound algorithm for finding optimal solutions for this problem. The algorithm partitions the channels into boxes and searches for the optimal among the various mappings of the horizontal net segments to the boxes. The authors discuss three different branching strategies for the algorithm. Heuristic algorithms based on the branching strategies are also discussed. It is also shown that VHV routing is NP-hard for irregular channels.>

In VLSI design, technology requirements often dictate the use of only two orthogonal orientations, determining both the shape of objects and the distance function, the $L_1 $-metric, to be used for wiring objects. More recent VLSI fabrication technology is capable of creating edges and wires in both the orthogonal and diagonal orientations. We generalize the distance concept to the case where any fixed set of orientations is allowed, and introduce a family of naturally induced metrics, and the subsequent generalization of geometrical concepts. A shortest connection between two points is in this case a path composed of line segments with only the given orientations. We derive optimal solutions for various basic planar distance problems in this setting, such as the computation of a Voronoi diagram, a minimum spanning tree, and the (minimum and maximum) distance between two convex polygons. Many other theoretically interesting and practically relevant problems remain to be solved. In particular, the new family of metrics may help bridge the gap between the $L_1 $- and $L_2 $-metrics, as those are the limiting cases for two and infinitely many regularly distributed orientations.

In this paper we consider the problem of optimal wiring of VLSI circuits. The topological placement of the circuit elements (macros) on the chip is assumed to have a special hierarchical structure, i.e., to be a slicing floorplan, represented by a binary (slicing) tree. Instead of the usual objective of minimum wire length, we consider the problem of minimizing the overall area of the wired floorplan. For the case of a single multiterminal net connecting n macros, we obtain a wiring algorithm of complexity O(nd), where d is the depth of the slicing tree. The case of several multiterminal nets is still under investigation.

We study the rectilinear shortest paths and minimum spanning tree (MST) problems for a set of points in the plane in the presence of rectilinear obstacles. We use the track graph, a suitably defined grid-like structure, to obtain efficient solutions for both problems. The track graph consists of rectilinear tracks defined by the obstacles and the points for which shortest paths and a minimum spanning tree are sought. We use a growth process like Dijkstra's on the track graph to find shortest paths from any point in the set to all other points (the one-to-all shortest paths problem). For the one-to-all shortest paths problem for n points we derive an O(n min {log n, log e} + (e + k) log t) time algorithm, where e is the total number of edges of all obstacles, t is the number of extreme edges of all obstacles, and k is the number of intersections among obstacle tracks (all bounds are for the worst case). The MST for the points is constructed also in time O(n log n + (e + k) log t) by a hybrid method of searching for shortest paths while simultaneously constructing an MST. An interesting application of the MST algorithm is the approximation of Steiner trees in graphs.

We present a global wiring algorithm used in a top-down physical design environment, i.e., macros are laid out after global wiring is done, and wires are allowed to pass through macros (the wiring-through model). The floorplan of the chip is in the form of a slicing structure. The algorithm is based on a hierarchical scheme. The final result is obtained through a series of refinement as the problem is recursively decomposed into a set of small-sized problems and then solved efficiently. The worst-case run-time for an arbitrary slicing tree (totally skewed) is O(M /sup 2/ N). When the floorplan is represented by a balanced slicing tree, the run-time of the overall algorithm is O(MN), where M is the number of macros and N the number of nets. The algorithm has been implemented in the C language and is used for chip designs. Experiments on both real and randomly generated designs show that the hierarchical router performs equally well as a flat global router in terms of wire length and wireability handling, but much faster in run-time (at least 10 times for an example with 100 macros and 1000 nets, and the gap being even larger for bigger-size problems).

We present a global wiring algorithm used in a top-down physical design environment, i.e. macros are laid out only after global wiring is done, and wires are allowed to pass through macros (wiring-through model). The floorplan of the chip is in the form of a slicing structure. The algorithm is based on a hierarchical scheme. The final result is obtained through a series of refinement as the problem is recursively decomposed into a set of small-sized problems and then solved efficiently. Given a balanced slicing tree representation of the floorplan, the worst-case running time of the overall algorithm is O(MN), where M is the number of macros and N the number of nets. The algorithm has been implemented in the C language and has been used for actual chip design. Experiments showed that the hierarchical router performs better than a flat maze type router in wireability handling, equally well in wire length, and much faster in run-time (at least 10 times for an example with 100 macros and 1000 nets, and the gap being even larger for bigger sized problems).

In computational geometry, problems involving only rectilinear objects with edges parallel to the x -and y-axes have attracted great attention. They are often easier to solve than the same problems for arbitrary objects, and solutions are of high practical value, for instance in VLSI design. This is because in VLSI design technology requirements often dictate the use of only two orthogonal orientations for the boundary edges of objects as well as wires.

In this paper, a problem in macro design using cascode-switch tree logic is studied. It involves selecting specific tree instantiations of Boolean functions and input variable assignments to maximize the alignment of variables between adjacent trees. An algorithm to find optimal solutions based on the principle of optimality is proposed. Although in general it is not a polynomial time algorithm, it runs sufficiently fast for our practical application. Finally we prove the problem is NP-complete, thus the existence of polynomial time algorithms is indeed unlikely.

In this paper, we investigate the problem of constructing a TDMA frame for a multibeam satellite system. Our objective is to permit the transmission of a given pattern of traffic, while ensuring that the number of times that the on-board switch needs to be reconfigured is minimized. We find that the underlying optimization problem is computationally intractable, but go on to suggest an efficient heuristic algorithm which we validate through experiments on randomly generated traffic patterns.

In this paper, we study a special class of trees called $\alpha $-$\beta $ leaf trees with degree r. These trees arise in information retrieval problems as well as prefix coding problems. An efficient method for constructing optimal trees is presented. The method is combinatorial in nature instead of the integer programming approach followed by other authors to study similar problems. The construction time is linear to the number of leaves of the tree.

In this paper we consider the problem of local wiring in a VLSI chip. The problem is one of interconnecting two sets of terminals, one set on each side of a wiring channel, in accordance with a given interconnection pattern, and to accomplish this while minimizing some objective function. We make the further assumption that the terminals are not rigidly positioned and can be "moved" provided that this does not change the structural intent of the circuit. Several objective functions are considered-channel width, channel length, channel area, channel perimeter, number of via holes, as well as some constrained objective functions. For some of these objective functions, we are able to find polynomial time optimal algorithms while, for others, we prove NP-completeness and suggest efficient heuristics.

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.

In this paper we study the traffic scheduling problem in an SS/TDMA system with interfering beams. We investigate a twostep approach, the first step being the assignment of orthogonal polarization to reduce the interference, and the second step being the scheduling of traffic, taking into account the "resultant" interference. The first step we show can be solved in polynomial time in most cases, while the second step we prove to be NP-complete, even for very simple interference patterns. We suggest several suboptimal algorithms for this second step and, by experimental trials on randomly generated traffic patterns, show that on the average they produce close to optimal solutions.

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.

In this paper we consider the generating, ranking, and unranking of 2-3 trees with n keys. We propose a linear ordering among these trees. The problem of ranking is to determine the rank of a given tree in this ordering, while unranking means constructing the tree of a given rank. The main result is that ranking and unranking can be done in $O(n)$ time after a preprocessing step that takes $O(n^2 )$ time and space.

In this paper we consider an SS/TDMA system withMuplink beams andNdownlink beams, where uplink beamihas bandwidth βiand downlink beamjhas bandwidth αj. The maximum traffic which can be handled by the satellite (in any given time slot) is assumed to beK. Multiplexing and demuitiplexing are also assumed. An optimal time slot assignment algorithm to minimize the total transmission time for any given traffic demand matrix is proposed and analyzed. Other system configurations of interest are also discussed.

In this paper, we examine the problem of time-slot assignment in an SS/TDMA system operating in a packet-switched environment. We seek to assign time slots in order to minimize average packet waiting time and in order to maximize transponder utilization. We show that an assignment which achieves both objectives exists and develop a branch-and-bound algorithm to find it. In addition, we suggest several heuristics which require much less computational effort and give very close to optimal results. We derive theoretical bounds on the performance of these heuristics and perform simulation trials to show that, on average, the heuristics are very much better than their bounds suggest, and are, in fact, extremely close to optimal.

Encryption is used in a communication system to safeguard information in the transmitted messages from anyone other than the intended receiver(s). To perform the encryption and decryption the transmitter and receiver(s) ought to have matching encryption and decryption keys. A clever way to generate these keys is to use the public key distribution system invented by Diffie and Hellman. That system, however, admits only one pair of communication stations to share a particular pair of encryption and decryption keys, The public key distribution system is generalized to a conference key distribution system (CKDS) which admits any group of stations to share the same encryption and decryption keys. The analysis reveals two important aspects of any conference key distribution system. One is the multitap resistance, which is a measure of the information security in the communication system. The other is the separation of the problem into two parts: the choice of a suitable symmetric function of the private keys and the choice of a suitable one-way mapping thereof. We have also shown how to use CKDS in connection with public key ciphers and an authorization scheme.

In this paper we analyze various search schemes in a major/minor loop bubble memory. Specifically, we study balanced tree search, one-sided height-balanced tree search, and one-sided K-Keight-balanced tree search. Two parameters are of interest in the present framework, namely, the number of comparisons and the amount of record movement required for a search. One-sided height- balanced tree search seems to offer the best compromise. Other related issues such as insertion and deletions are also discussed.

Two generic record-permutation bubble devices—the bubble ladder and the bubble string comparator—have been reported in the literature but not yet implemented. The former relies on the extensive use of external control lines, while the latter relies solely on the interaction between bubbles. The ladder has evolved into an odd- even sorter and then a rebound sorter, but, uufortunately, it is operated by a large number of control lines. This paper shows that equally efficient but more versatile sorters can be constructed from the bubble string comparators without the control lines. Moreover, the new sorter—an up-down sorter—will be implemented in the recently invented high-density, high-speed, coil-less perforated-sheet bubble devices.

In this paper we consider an SS/TDMA system withMuplink beams,Ndownlink beams, andK, 1 \leq K \leq \min (M, N)transponders. An optimal time slot assignment algorithm for anyM, N, K,and any traffic matrix is presented, where optimality means achieving the minimal possible total duration for the given traffic matrix. The number of switching matrices generated by the algorithm is bounded above byN^{2} - N + 1forK = M = NandMN + K + 1otherwise. Extensive simulation results on randomly generated matrices are carried out, showing that the average number of switching matrices generated is substantially lower than the bounds.

In this paper we consider an SS/TDMA system withMuplink beams,Ndownlink beams, andKconnection points. We first assume that the downlink is α times faster than the uplink, and a simple time multiplexing scheme is employed. An optimal time slot assignment algorithm for anyM, N,\alpha, andK,1 \leq K \leq \min (M, \alphaN), and for any traffic matrix is presented, where optimality means achieving the minimal possible total transmission time for the given traffic matrix. The number of switching matrices generated by the algorithm never exceedsMN + K\alpha + 1. Extensive simulation results on randomly generated matrices are carried out, showing that the average number of switching matrices generated is substantially lower than the upper bound. The case when the uplink is faster than the downlink is also considered.

Encryption is an efficient method for information protection in communication links which are subject to wiretapping. In this paper we discuss the application of encryption to satellite communication systems in which the satellite has on-board processing capability. The on-board processor can be used in the key distribution process. Two examples of such processes are described. The first requires the storage in the satellite of one key for each user of the communication system. These are used together with a conventional encryption algorithm (DES, for example) to distribute communication keys to the users. The communication keys are then used to encrypt and decrypt information. The other key distribution process utilizes a trap-door one-way function, whose inverse is implemented in the satellite. The need for storage space in the satellite is smaller than that with the first method.

In this paper we study the problem of scheduling the read/write head movement to handle a batch of $nI/O$ requests in a 2-dimensional secondary storage device in minimum time. Two models of storage systems are assumed in which the access time of a record (being proportional to the “distance” between the position of the record and that of the read/write head) is measured in terms of $L_1 $ and $L_\infty $ metrics, respectively. The scheduling problem, referred to as the Open Path Problem (OPP), is equivalent to finding a shortest Hamiltonian path with a specified end point in a complete graph with n vertices. We first show in this paper that there exists a natural isometry between the $L_1 $ and $L_\infty $ metrics. Consequently, the existence of a polynomial time algorithm for the OPP in one metric implies the existence of a polynomial time algorithm for the same problem in the other metric. Based on a result by Garey, Graham and Johnson, it is easy to show that the OPP in $L_1 $ (hence in $L_\infty $) metric is $NP$-complete. A heuristic to solve the OPP is therefore presented. It is based on a geometric structure called the Voronoi diagram in $L_1 $ metric. An optimal (worst-case) algorithm of time complexity $O(n\log n)$ for constructing the diagram for a set of n points in a plane is described. Using this diagram one can build a near-optimal path through each point either by constructing a minimum spanning tree or by the closest insertion method. Both algorithms are shown to take $O(n\log n)$ time which is the time for the construction of the diagram and yield an approximate solution within a factor of 2. The bound is also shown to be tight in the worse case. For the average case, simulation results show that the minimum spanning tree approach is better than the closest insertion method. As expected, they are far better than the sequential one in which the request is processed one at a time on the first-come–first-served basis.

In this note, an efficient method for weighted sampling of K objects without replacement from a population of n objects is proposed. The method requires $O(K\log n)$ additions and comparisons, and $O(K)$ multiplications and random number generations while the method proposed by Fagin and Price requires $O(Kn)$ additions and comparisons, and $O(K)$ divisions and random number generations.

In this paper the problem of sorting in various models of magnetic bubble memory systems is studied. Three basic parameters are of interest, namely, the number of steps to sort, the number of switches required, and the number of control states necessary for the switches. Several sorting algorithms are proposed with respective running times essentially n2, n/2, 1/2 n log2 n, 7/2 n, n log2n, respective numbers of switches essentially, 1, n, 2√n, 2√nlog2n , 1og2n, and respective numbers of control states essentially, 3, 2, 1/8 log2n, 1/8 log2n, and 3 log2n.

In this paper, we study the problem of maintaining a file in magnetic bubble memories. A memory structure with a special loop ordering scheme is proposed, in which records are stored in a balanced tree form. Algorithms for searching, insertion, and deletion are proposed. They have the property that, after each operation, the file is restored to a balanced tree form. The searching operation takes time log22 n/(2 log2 log2 n) + O(log2 n) where n is the number of records in the file, while insertion and deletion take additional log2 n + O(1) time each. This scheme, however, requires that each switch be individually settable. In the latter part of the paper, the memory is slightly modified, and a new loop ordering scheme proposed. With only two control operations, we show that searching, insertion, and deletion of records in the tree can still be done although the tree can no longer be kept in balanced form. If the tree is balanced, then searching, insertion, and deletion take only 5/2 log2 (n + 1) + O(1) time each.

In this correspondence we present a simple construction of a generalized connector with 5.8n log2n edges, which is an improvement over a previous construction proposed by Thompson and requiring 7.6n log2n edges. Specifically, we propose a construction for a generalizer with only 2n log2n edges as against that proposed by Thompson with 3.8n log2n edges.

article Free Access Share on Quintary trees: a file structure for multidimensional datbase sytems Authors: D. T. Lee Northwestern Univ., Evanston, IL Northwestern Univ., Evanston, ILView Profile , C. K. Wong IBM Thomas J. Watson Research Center, Yorktown Heights, NY IBM Thomas J. Watson Research Center, Yorktown Heights, NYView Profile Authors Info & Claims ACM Transactions on Database SystemsVolume 5Issue 3Sept. 1980 pp 339–353https://doi.org/10.1145/320613.320618Published:01 September 1980Publication History 64citation559DownloadsMetricsTotal Citations64Total Downloads559Last 12 Months29Last 6 weeks5 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

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”.

Given two finite sets of k-tuples whose component elements are drawn from an infinite totally ordered set, the problem of identifying the k-tuples which belong to both sets is considered. Attention is restricted to algorithms that perform pairwise comparisons on the component elements of the k-tuples. If the two sets have cardinalities m and n with $m \leqq n$ it is shown that, in the worst case, \[ (m + n) \cdot \log _2 m + (m + n - 1)k \] comparisons are sufficient and \[ \max ((m + n) \cdot \log _2 m - 2.9m,(m + n - 1)k) \] comparisons are necessary. Upper and lower bounds are also given for the number of comparisons required to recognize duplicate tuples in a sequence of tuples, and to determine the lexicographic order of a sequence of tuples. In all cases, the disparity between the upper and lower bounds is at most a factor of two asymptotically.

In this paper, we propose a layout of access channels in a new kind of magnetic bubble memory called a bubble lattice file. We further assume that interchange of bubble columns under certain channels is possible. We then propose an algorithm for moving a column to any other location using minimal number of column interchanges. The algorithm and the proof of its optimality involves signed-digit representation of numbers by a mixed radix system. Based on this, we next propose a simple algorithm to permute a set of columns. Analysis of this algorithm for both the worst and average case is given. The algorithm is shown to be close to optimal for both cases. Finally, based on an optimization consideration, a geometric layout of access channels is suggested for the best performance of the proposed algorithm.

Some special classes of interconnection networks for n terminals are considered, namely, partitioning networks and full switches. Constructions for them are presented. For the former, the resulting total count of (two-state) cels is n log2n + n − log2n − 1, and the maximum delay is 6 log2n − 4. For the latter, the cell count is (n/2)log2n − (n/2) and the maximum delay is 2 log2n − 1. By establishing appropriate lower bounds, we show that these networks are asymptotically optimal as far as cell count is concerned.

This paper considers allocation of space in a hnear storage medium when space must be allocated dynamically as customers arrive A heuristic is proposed for this problem and for a simple model of the resultmg reference sequence, we show that the average distance between consecutive references is asymptotically 7n/30, where n is the size of the storage For optimal static placement where one waits for all arrivals before any space allocation, the average distance is shown to be asymptotically 7n/30 For random placement, the average distance is asymptotically n/3 Thus, the heuristic is asymptotically optimal in a strong sense For reasonable values of n, we demonstrate that the heuristic is nearly as good as optimal static placement and much better than random placement KEY WORDS AND PHRASES minimization of disk seek time, minidisks, linear store, dynamic allocation of storage space, concrete complexity, optimal algorithms, asymptotically optimal algorithms, analysts of algorithms, heuristics CR CATEGORIES 4 35, 5 25 Notational ConventionsWe must deal with a set of n users who arrive at n distinct points in time, and who are General permission to make fair use in teachmg or research of all or part of this material is granted to individual readers and to nonprofit libraries acting for them provided that ACM's copyright notice ts given and that reference is made to the publication, to its date of issue, and to the fact that reprinting privileges were granted by

The general knapsack problem is known to be NP-complete. In this paper a very special knapsack problem ia studied, namely, one with only two variables. A polynomial-time algorithm is presented and analyzed. However, it remains an open problem that for any fixed n > 2, the knapsack problem with n variables can be solved in polynomial time.

The string editing problem is to determine the distance between two strings as measured by the minimal cost sequence of deletions, insertions, and changes of symbols needed to transform one string into the other. The longest common subsequence problem can be viewed as a special case. Wagner and Fischer proposed an algorithm that runs in time O ( nm ), where n, m are the lengths of the two strings. In the present paper, it is shown that if the operations on symbols of the strings are restricted to tests of equality, then O ( nm ) operations are necessary (and sufficient) to compute the distance.

In this paper two recent models of basic operations in magnetic bubble memories are discussed. The accessing of an item and the generation of arbitrary permutations in these models are studied. It is shown that the two methods of accessing an item as described in this paper for the two models are optimal in terms of the number of operations. For each model, lower bounds for the number of operations needed to generate arbitrary permutations are derived for both the worst case and the average case. Consequently, the methods proposed in this paper for both models are shown to be optimal as far as the order of magnitude of the number of operations is concerned. The results obtained in this paper may be helpful for deciding upon the relative merits of these two models.

article Free Access Share on The Effect of a Capacity Constraint on the Minimal Cost of a Partition Authors: C. K. Wong IBM Thomas J. Watson Research Center, P O. Box 218, Yorktown Heights, NY IBM Thomas J. Watson Research Center, P O. Box 218, Yorktown Heights, NYView Profile , M. C. Easton IBM Thomas J. Watson Research Center, P O. Box 218, Yorktown Heights, NY IBM Thomas J. Watson Research Center, P O. Box 218, Yorktown Heights, NYView Profile Authors Info & Claims Journal of the ACMVolume 22Issue 4Oct. 1975 pp 441–449https://doi.org/10.1145/321906.321907Online:01 October 1975Publication History 9citation325DownloadsMetricsTotal Citations9Total Downloads325Last 12 Months7Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

In this paper, a discrete minimization problem arising from storage allocation considerations is studied. Owing to the complexity of finding an optimum solution, a heuristic is proposed and its performance is analyzed. The worst-case ratio of the cost by this algorithm to that by the optimum algorithm is shown to lie between 1.03 and 1.04, implying that this algorithm produces a solution within 4 per cent of the optimum. A generalization of this problem to a class of cost functions is also considered. The worst-case ratios for these functions tend, in the limit, to that of the cost function studied by Graham in his classical paper [1].

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.

This paper deals with a combinatorial minimization problem arising from studies on multimodule memory organizations. Instead of searching for an optimum solution, a particular solution is proposed and it is demonstrated that it is close to optimum. Lower bounds for the objective functions are obtained and compared with the corresponding values of the particular solution. The maximum percentage deviation of this solution from optimum is also established.

A method of constructing binary search trees in a multiprocessor computer system is proposed. Asymptotically, this method achieves the maximum possible increase in speed as compared with a single processor computer system. To make better use of this method, a parametrized restructuring of binary search trees is also discussed.

Two upper bounds for the total path length of binary trees are obtained. One is for node-trees, and bounds the internal (or root-to-node) path length; the other is for leaf-trees, and bounds the external (or root-to-leaf) path length. These bounds involve a quantity called the balance, which allows the bounds to adapt from the n log n behavior of a completely balanced tree to the n 2 behavior of a most skewed tree. These bounds are illustrated for the case of Fibonacci trees.

It is shown that a natural partitioning scheme based on the ranking of access probabilities is optimal in three specific storage applications.These applications include organization of an archival store, disk space allocation, and pagination.The use of Schur functions as an optimization technique is introduced.

A control method based on anticipatory shift with lookahead is proposed for accessing files stored in a cyclically permutable memory as characterized by, for example, bubble-domain devices. The performance of this method is analyzed and is shown to yield significant reduction of access time. By using a basic simple model, an explicit formula is obtained for relating performance to the size of requests, the shift register length, and the number of control sections allowed. Several generalizations are also discussed.