12439298
The Steiner Tree Problem in Orientation Metrics
Given a set?of?i(i=1,2,?,k) orientations (angles) in the plane, one can define a distance function which induces a metric in the plane, called the orientation metric 3. In the special case where all the angles are equal, we call the metric a uniform orientation metric 2. Specifically, if there are?orientations, forming anglesi?/?, 0?i???1, with thex-axis, where??2 is an integer, we call the metric a??-metric. Note that the?2-metric is the well-known rectilinear metric and the?∞corresponds to the Euclidean metric. In this paper, we will concentrate on the?3-metric. In the?2-metric, Hanan has shown that there exists a solution of the Steiner tree problem such that all Steiner points are on the intersections of grid lines formed by passing lines at directionsi?/2,i=0,1, through all demand points. But this is not true in the?3-metric. In this paper, we mainly prove the following theorem: LetP,Q, andOi(i=1,2,?,k) be the set ofndemand points, the set of Steiner points, and the set of theith generation intersection points, respectively. Then there exists a solutionGof the Steiner problemSnsuch that all Steiner points are in ?ki=1Oi, wherek?? (n?2)/2?.
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.
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.
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”.
1861595
Charge optimization of the interface between protein kinases and their ligands
Examining the potential for electrostatic complementarity between a ligand and a receptor is a useful technique for rational drug design, and can demonstrate how a system prioritizes interactions when allowed to optimize its charge distribution. In this computational study, we implemented the previously developed, continuum solvent-based charge optimization theory with a simple, quadratic programming algorithm and the UHBD Poisson-Boltzmann solver. This method allows one to compute the best set of point charges for a ligand or ligand region based on the ligand and receptor shape, and the receptor partial charges, by optimizing the binding free energy obtained from a continuum-solvent model. We applied charge optimization to a fragment of the heat-stable protein kinase inhibitor (PKI) of protein kinase A (PKA), to three flavopiridol inhibitors of CDK2, and to cyclin A which interacts with CDK2 to regulate the cell cycle. We found that a combination of global (involving every charge) and local (involving only charges in a local region) optimization can give useful hints for designing better inhibitors. Although some parts of an inhibitor may already contribute significantly to binding, we found that they could still be the most important targets for modifications to obtain stronger binders. In studying the binding of flavopiridol inhibitors to CDK2, comparable binding affinity could be obtained regardless of whether the net charges of the inhibitors were constrained to -2, -1, 0, 1, or 2 during the optimization. This provides flexibility in inhibitor design when a certain net charge of the inhibitor is desired in addition to strong binding affinity. For the study of the PKA-PKI and CDK2-cyclin A interfaces, we identified residues whose charge distributions are already close to optimal and those whose charge distributions could be refined to further improve binding.
43443657
A note on visibility graphs
Abstract Given a set S = {s1, s2,…, sn} of vertical line segments, s1, sj see each other if there is a horizontal line segment which intersects them, but does not intersect any other line segment between them. A visibility graph G of vertices {v1, v2,…, vn} is put into a one-to-one correspondence with S, such that si corresponds to v1, and edge {vi, vj} exists in G iff si, sj see each other. We prove that any visibility graph G is ipo-triangular, that is, it can be transformed into a planar multigraph with all triangular finite faces, by successive duplications of existing edges of G. Conversely we prove that any ipo-triangular graph is a visibility graph for some set S.
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.
38611039
Vertex Ranking of Asteroidal Triple-Free Graphs
We present an efficient algorithm for computing the vertex ranking number of an asteroidal triple-free graph. Its running time is bounded by a polynomial in the number of vertices and the number of minimal separators of the input graph.
46500499
Minimum Fill-in on Circle and Circular-Arc Graphs
We present two algorithms solving the minimum fill-in problem on circle graphs and on circular-arc graphs in timeO(n3).