-
Article
Approximations for Steiner Trees with Minimum Number of Steiner Points
Given n terminals in the Euclidean plane and a positive constant, find a Steiner tree interconnecting all terminals with the minimum number of Steiner points such that the Euclidean length of each edge is no more...
-
Article
An Efficient Algorithm for Delay Buffer Minimization
A data flow machine is said to be synchronized if for any vertex u in the underlying data flow graph, all inputs to vertex u arrive at the same time. An unsynchronized data flow machine with an acyclic underly...
-
Chapter
Grade of Service Steiner Trees in Series-Parallel Networks
The grade of service Steiner tree problem is to determine the minimum total cost of an assignment of a grade of service to each link in a network, so that between each pair of nodes there is a path whose minim...
-
Article
Optimization of Molecular Similarity Index with Applications to Biomolecules
Molecular similarity index measures the similarity between two molecules. Computing the optimal similarity index is a hard global optimization problem. Since the objective function value is very hard to comput...
-
Chapter and Conference Paper
Signed Genome Rearrangement by Reversals and Transpositions: Models and Approximations
An important problem in computational molecular biology is the genome rearrangement using reversals and transpositions. Analysis of genome evolving by inversions and transpositions leads to a combinatorial opt...
-
Chapter
Finite Behavior of Simulated Annealing: A Probabilistic Study
Simulated annealing (SA) is a simple global optimization method that has been used extensively in various applications, ranging from the study of molecular clusters to combinatorial optimization problems in VL...
-
Chapter and Conference Paper
The Steiner Tree Problem in λ4-geometry Plane
In this paper, we study the Steiner tree problem in the λ4-geometry plane in which any line, half line or line segment must go in an orientation of iπ/4 with the positive x-axis, 0 ≤ i ≤ 7, and the distance betwe...
-
Chapter and Conference Paper
A Cost Optimal Parallel Algorithm for Computing Force Field in N-Body Simulations
We consider the following force field computation problem: given a cluster of n particles in 3-dimensional space, compute the force exerted on each particle by the other particles. Depending on different applicat...
-
Article
Copmputer Simulations in Molecular and Protein Conformations
-
Chapter and Conference Paper
A branch-and-bound algorithm for computing node weighted steiner minimum trees
Given n regular points in the Euclidean plane, the node-weighted Steiner minimum tree (NWSMT) is a straight line network interconnecting these n regular points and some Steiner points with a minimum cost, where t...
-
Chapter and Conference Paper
O(n log n)-average-time algorithm for shortest network under a given topology
In 1992, F.K. Hwang and J.F. Weng published an O(n 2) operation algorithm for computing the shortest network under a given full Steiner topology interconnecting n fixed points in the Euclidean plane. The Hwang-We...
-
Chapter
Parallel algorithms for global optimization problems
-
Article
On an open problem in spherical facility location
In this paper we partially resolve an open problem in spherical facility location. The spherical facility location problem is a generalization of the planar Euclidean facility location problem. This problem wa...
-
Chapter
The Spherical One-Center Problem
In this paper we study the spherical one-center problem, i. e., finding a point on a sphere such that the maximum of the geodesic distances from this point to n given points on the sphere is at minimum. We show t...
-
Article
Improvement on the northby algorithm for molecular conformation: Better solutions
In 1987, Northby presented an efficient lattice based search and optimization procedure to compute ground states ofn-atom Lennard-Jones clusters and reported putative global minima for 13⩽n⩽150. In this paper, we...
-
Article
Preface
-
Article
Molecular conformation on the CM-5 by parallel two-level simulated annealing
In this paper, we propose a new kind of simulated annealing algorithm calledtwo-level simulated annealing for solving certain class of hard combinatorial optimization problems. This two-level simulated annealing ...
-
Article
Optimization methods for computing global minima of nonconvex potential energy functions
The minimization of potential energy functions plays an important role in the determination of ground states or stable states of certain classes of molecular clusters and proteins. In this paper we introduce s...
-
Chapter and Conference Paper
Achieving the shortest clock period by inserting the minimum amount of delay
The performance of a circuit depends on its clock period. The shorter a valid clock period is, the better the performance is. The clock period is tightly related to the difference between the longest propagati...
-
Chapter
The Euclidean Facilities Location Problem
The facilities location problem is one of locating new facilities with respect to existing facilities, the locations of which are known. The problem consists of finding locations of new facilities which will m...
