This paper derives the optimal trajectories in a general fluid network with server control. The stationary optimal policy in the complete state space is constructed. The optimal policy is constant on polyhedral convex cones. An algorithm is derived that computes these cones and the optimal policy. Generalized Klimov indices are introduced, they are used for characterizing myopic and time-uniformly optimal policies.Received: November 2004 / Revised: February 2005The research of this author has been supported by the project ‘‘Stochastic Networks’’ of the Netherlands Organisation for Scientific Research NWO. 相似文献
We consider the following problem: given a set of points in the plane, each with a weight, and capacities of the four quadrants, assign each point to one of the quadrants such that the total weight of points assigned to a quadrant does not exceed its capacity, and the total distance is minimized.
This problem is most important in placement of VLSI circuits and is likely to have other applications. It is NP-hard, but the fractional relaxation always has an optimal solution which is “almost” integral. Hence for large instances, it suffices to solve the fractional relaxation. The main result of this paper is a linear-time algorithm for this relaxation. It is based on a structure theorem describing optimal solutions by so-called “American maps” and makes sophisticated use of binary search techniques and weighted median computations.
This algorithm is a main subroutine of a VLSI placement tool that is used for the design of many of the most complex chips. 相似文献
For the Na I2 collision system, theoretical study is performed on the QCISD(T) level by using ab initio method. The ab initio potential energy surfaces are got and on them the long-lived complexes are found and optimized. These results verify the crossed molecule beam experimental phenomenon and the detailed geometry structures are given for the first time. The role of the complexes in the reaction path is also described in detail. 相似文献
If 1≤k≤n, then Cor(n,k) denotes the set of all n×n real correlation matrices of rank not exceeding k. Grone and Pierce have shown that if A∈Cor (n, n-1), then per(A)≥n/(n-1). We show that if A∈Cor(n,2), then , and that this inequality is the best possible. 相似文献
Efficient sequential quadratic programming (SQP) implementations are presented for equality-constrained, discrete-time, optimal control problems. The algorithm developed calculates the search direction for the equality-based variant of SQP and is applicable to problems with either fixed or free final time. Problem solutions are obtained by solving iteratively a series of constrained quadratic programs. The number of mathematical operations required for each iteration is proportional to the number of discrete times N. This is contrasted by conventional methods in which this number is proportional to N3. The algorithm results in quadratic convergence of the iterates under the same conditions as those for SQP and simplifies to an existing dynamic programming approach when there are no constraints and the final time is fixed. A simple test problem and two application problems are presented. The application examples include a satellite dynamics problem and a set of brachistochrone problems involving viscous friction. 相似文献