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.
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.
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”.
12009161
Dynamic Placement of Records in Linear Storage
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
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. >
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.
1566543
Minimizing Mean Flow Time with Error Constraint
Abstract. We consider the problem of minimizing mean flow time for the Imprecise Computation Model introduced by Lin et al. A task system TS=({Ti},{r(Ti)},{d(Ti)},{m(Ti)},{o(Ti)})  consists of a set of n  independent tasks, where r(Ti),d(Ti),m(Ti) , and o(Ti)  denote the ready time, deadline, execution time of the mandatory part, and execution time of the optional part of Ti , respectively. Given a task system TS  and an error threshold K , our goal is to find a preemptive schedule on one processor such that 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. In this article we show that the problem of finding an optimal schedule is NP-hard, even if all tasks have identical ready times and deadlines. A pseudopolynomial-time algorithm is given for a set of tasks with identical ready times and deadlines, and oppositely ordered mandatory execution times and total execution times (i.e., there is a labeling of tasks such that m(Ti)≤ m(Ti+1)  and m(Ti)+o(Ti)≥ m(Ti+1)+o(Ti+1)  for each 1≤ i<n  ). Finally, polynomial-time algorithms are given for (1) a set of tasks with identical ready times, and similarly ordered mandatory execution times and total execution times and (2) a set of tasks with similarly ordered ready times, deadlines, mandatory execution times, and total execution times.
654791
An image signature for any kind of image
We describe an algorithm for computing an image signature, suitable for first-stage screening for duplicate images. Our signature relies on the relative brightness of image regions, and is generally applicable to photographs, text documents, and line art. We give experimental results on the sensitivity and robustness of signatures for actual image collections, and also results on the robustness of signatures under transformations such as resizing, rescanning, and compression.
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.
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.
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>>