Library

X
feed icon rss

Your email was sent successfully. Check your inbox.

An error occurred while sending the email. Please try again.

Proceed reservation?

Export
  • 1
    Electronic Resource
    Electronic Resource
    An Efficient Algorithm for Delay Buffer Minimization (2000)
    Springer
    Journal of combinatorial optimization 4 (2000), S. 217-233 
    Details
    ISSN: 1573-2886
    Keywords: VLSI technology ; data flow machine ; optimal delay buffer insertion
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract 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 underlying data flow graph can be transformed into a synchronized system by adding unit delay buffers to the system. This synchronization process can increase pipelining and throughout. Since the addition of delay buffers introduces hardware and area costs, it is desirable to insert the minimum number of delay buffers to synchronize a given data flow machine. Due to important applications in computer design, various delay buffer minimization problems have been studied by many researchers. Several optimal algorithms and heuristic algorithms have been proposed for slightly different models. In this paper, we introduce the concept of extensions of a directed acyclic graph to generalize and formalize several delay buffer minimization problems studied in the literature and present a polynomial time algorithm for computing the minimum delay buffer synchronization of a given data flow machine. Examples are provided to illustrate our algorithm and to show that our algorithm requires fewer delay buffers than previously published optimal algorithms for various models.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1023/A:1009850721462
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    Improvement on the northby algorithm for molecular conformation: Better solutions (1994)
    Springer
    Journal of global optimization 4 (1994), S. 425-440 
    Details
    ISSN: 1573-2916
    Keywords: Molecular conformation ; data structures ; improved algorithms ; better solutions
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract 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 introduce simple data structures which reduce the time complexity of the Northby algorithm for lattice search fromO(n5/3) per move toO(n2/3) per move for ann-atom cluster involving full Lennard-Jones potential function. If nearest neighbor potential function is used, the time complexity can be further reduced toO(logn) per move for ann-atom cluster. The lattice local minimizers with lowest potential function values are relaxed by a powerful Truncated Newton algorithm. We are able to reproduce the minima reported by Northby. The improved algorithm is so efficient that less than 3 minutes of CPU time on the Cray-XMP is required for each cluster size in the above range. We then further improve the Northby algorithm by relaxingevery lattice local minimizer found in the process. This certainly requires more time. However, lower energy configurations were found with this improved algorithm forn=65, 66, 75, 76, 77 and 134. These findings also show that in some cases, the relaxation of a lattice local minimizer with a worse potential function value may lead to a local minimizer with a better potential function value.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01099267
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    Optimization of Molecular Similarity Index with Applications to Biomolecules (1999)
    Springer
    Journal of global optimization 14 (1999), S. 299-312 
    Details
    ISSN: 1573-2916
    Keywords: Computational biology ; Global optimization ; Molecular similarity
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract 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 compute and its gradient vector is usually not available, previous research has been based on non-gradient algorithms such as random search and the simplex method. In a recent paper, McMahon and King introduced a Gaussian approximation so that both the function value and the gradient vector can be computed analytically. They then proposed a steepest descent algorithm for computing the optimal similarity index of small molecules. In this paper, we consider a similar problem. Instead of computing atom-based derivatives, we directly compute the derivatives with respect to the six free variables describing the relative positions of the two molecules.. We show that both the function value and gradient vector can be computed analytically and apply the more advanced BFGS method in addition to the steepest descent algorithm. The algorithms are applied to compute the similarities among the 20 amino acids and biomolecules like proteins. Our computational results show that our algorithm can achieve more accuracy than previous methods and has a 6-fold speedup over the steepest descent method.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1023/A:1008206921290
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    Optimization methods for computing global minima of nonconvex potential energy functions (1994)
    Springer
    Journal of global optimization 4 (1994), S. 117-133 
    Details
    ISSN: 1573-2916
    Keywords: Molecular conformation ; protein folding ; nonconvex potential functions ; global optimization ; simulated annealing ; parallel algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract 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 some of the most commonly used potential energy functions and discuss different optimization methods used in the minimization of nonconvex potential energy functions. A very complete bibliography is also given.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01096719
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 5
    Electronic Resource
    Electronic Resource
    Molecular conformation on the CM-5 by parallel two-level simulated annealing (1994)
    Springer
    Journal of global optimization 4 (1994), S. 187-208 
    Details
    ISSN: 1573-2916
    Keywords: Molecular conformation ; global optimization ; simulated annealing ; parallel algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract 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 algorithm is less likely to get stuck at a non-global minimizer than conventional simulated annealing algorithms. We also propose a parallel version of our two-level simulated annealing algorithm and discuss its efficiency. This new technique is then applied to the Molecular Conformation problem in 3 dimensional Euclidean space. Extensive computational results on Thinking Machines CM-5 are presented. With the full Lennard-Jones potential function, we were able to get satisfactory results for problems for cluster sizes as large as 100,000. A peak rate of over 0.8 giga flop per second in 64-bit operations was sustained on a partition with 512 processing elements. To the best of our knowledge, ground states of Lennard-Jones clusters of size as large as these have never been reported before.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01096722
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 6
    Electronic Resource
    Electronic Resource
    Copmputer Simulations in Molecular and Protein Conformations (1997)
    Springer
    Journal of global optimization 11 (1997), S. V 
    Details
    ISSN: 1573-2916
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1023/A:1008231124556
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 7
    Electronic Resource
    Electronic Resource
    Approximations for Steiner Trees with Minimum Number of Steiner Points (2000)
    Springer
    Journal of global optimization 18 (2000), S. 17-33 
    Details
    ISSN: 1573-2916
    Keywords: Steiner trees ; Approximation algorithms ; VLSI design ; WDM optical networks
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract 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 than the given positive constant. This problem is NP-hard with applications in VLSI design, WDM optical networks and wireless communications. In this paper, we show that (a) the Steiner ratio is 1/ 4, that is, the minimum spanning tree yields a polynomial-time approximation with performance ratio exactly 4, (b) there exists a polynomial-time approximation with performance ratio 3, and (c) there exists a polynomial-time approxi-mation scheme under certain conditions.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1023/A:1008384012064
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 8
    Electronic Resource
    Electronic Resource
    Preface (1994)
    Springer
    Journal of global optimization 4 (1994), S. iii 
    Details
    ISSN: 1573-2916
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01096718
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 9
    Electronic Resource
    Electronic Resource
    On an open problem in spherical facility location (1995)
    Springer
    Numerical algorithms 9 (1995), S. 1-12 
    Details
    ISSN: 1572-9265
    Keywords: Spherical facility location ; Euclidean facility location ; closed form iteration formula ; open problem ; convergence theorem
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract 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 was first studied by Katz and Cooper and by Drezner and Wesolowsky where a Weszfeld-like algorithm was proposed. This algorithm is very simple and does not require a line search. However, its convergence has been an open problem for more than ten years. In this paper, we prove that the sequence generated by the algorithm converges to the unique optimal solution under the condition that the oscillation of the sequence converges to zero. We conjecture that the algorithm is a descent algorithm and prove that the sequence generated by the algorithm converges to the optimal solution under this conjecture.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02143923
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 10
    Electronic Resource
    Electronic Resource
    A globally convergent algorithm for the Euclidean multiplicity location problem (1992)
    Springer
    Acta mathematicae applicatae sinica 8 (1992), S. 357-366 
    Details
    ISSN: 1618-3932
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract The Euclidean single facility location problem (ESFL) and the Euclidean multiplicity location problem (EMFL) are two special nonsmooth convex programming problems which have attracted a large literature. For the ESFL problem, there are algorithms which converge both globally and quadratically. For the EMFL problem, there are some quadratically convergent algorithms, but for global convergence, they all need nontrivial assumptions on the problem. In this paper, we present an algorithm for EMFL. With no assumption on the problem, it is proved that from any initial point, this algorithm generates a sequence of points which converges to the closed convex set of optimal solutions of EMFL.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02006744
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...