Let P(lambda, mu) = min {f1(x) + lambda-f2(x) + mu-f3(x)\x is-an-element-of D}. We present a method that constructs P(lambda, mu) for all lambda, mu in a given interval in O(f.T(n) + f2) time, where f denotes the numb...
详细信息
Let P(lambda, mu) = min {f1(x) + lambda-f2(x) + mu-f3(x)\x is-an-element-of D}. We present a method that constructs P(lambda, mu) for all lambda, mu in a given interval in O(f.T(n) + f2) time, where f denotes the number of faces of P(lambda, mu) in the interval and T(n) denotes the time needed to solve the associated nonparametric problem.
作者：
XIN, YComputer Sciences Laboratory
Research School of Physical Sciences and Engineering The Australian National University Canberra ACT 2601 GPO Box 4 Australia
Simulated Annealing (SA) is a powerful stochastic search method applicable to a wide range of problems for which little prior knowledge is available. It can produce very high quality solutions for hard combinatorial o...
详细信息
Simulated Annealing (SA) is a powerful stochastic search method applicable to a wide range of problems for which little prior knowledge is available. It can produce very high quality solutions for hard combinatorial optimization problems. However, the computation time required by SA is very large. Various methods have been proposed to reduce the computation time, but they mainly deal with the careful tuning of SA'ol parameters. This paper first analyzes the impact of SA'neighbourhood on SA'performance and shows that SA with a larger neighbourhood is better than SA with a smaller one. The paper also gives a general model of SA, which has both dynamic generation probability and acceptance probability, and proves its convergence. All variants of SA can be unified under such a generalization. Finally, a method of extending SA's neighbourhood is proposed, which uses a discrete approximation to some continuous probability function as the generation function in SA, and several important corollaries of the general model are given.
It is shown that the proof of the main result in Reyner’s paper, similarly titled, is incorrect. Interestingly, by combining a simple modification of the algorithm with tighter analysis, one can obtain the original r...
详细信息
It is shown that the proof of the main result in Reyner’s paper, similarly titled, is incorrect. Interestingly, by combining a simple modification of the algorithm with tighter analysis, one can obtain the original result with a minor improvement.
We consider the problem of scheduling a partially ordered set of unit execution time (UET) tasks on m > 1 processors where there is a communication delay of unit time between any pair of distinct processors. We sho...
详细信息
We consider the problem of scheduling a partially ordered set of unit execution time (UET) tasks on m > 1 processors where there is a communication delay of unit time between any pair of distinct processors. We show that the problem of finding an optimal schedule is NP-hard. A greedy schedule is one where no processor remains idle if there is some task available which it could process. We establish that the length of an arbitrary greedy schedule, ω c g satisfies w c g 3− 2 m w c opt − 1− 1 m where ω c opt is the length of the optimal schedule. We define a generalized list schedule (a type of greedy schedule) and discuss anomalous behavour of such schedules with respect to speed-up. The relevance of these results to the implementation of parallel languages is discussed.
An examination is made of the problem of scheduling a set of independent tasks on a given number of identical processors. Preemption is allowed, but a communication delay is assumed. Whenever a task is preempted fro...
详细信息
An examination is made of the problem of scheduling a set of independent tasks on a given number of identical processors. Preemption is allowed, but a communication delay is assumed. Whenever a task is preempted from one processor to another, there has to be a delay of at least k time units. It is demonstrated that, if k is equal to one, an optimal schedule can be found in polynomial time but if k is greater than or equal to 2, the corresponding decision problem is NP-complete. It is very unlikely that there is a polynomial time algorithm to find an optimal k-delay schedule for the general case. Of course, this does not mean that no such algorithm exists for special cases. However, for the more general situation, suitable heuristics will be required.
algorithmic phase diagrams are a neat and compact representation of the results of comparing the execution time of several algorithms for the solution of the same problem. As an example we show the recent results of G...
详细信息
algorithmic phase diagrams are a neat and compact representation of the results of comparing the execution time of several algorithms for the solution of the same problem. As an example we show the recent results of Gannon and Van Rosendale on the solution of multiple tridiagonal systems of equations in the form of such diagrams. The act of preparing these diagrams has revealed an unexpectedly complex relationship between the best algorithm and the number and size of the tridiagonal systems, which was not evident from the algebraic formulae in the original paper. Even so, for a particular computer, one diagram suffices to predict the best algorithm for all problems that are likely to be encountered-the prediction being read directly from the diagram without complex calculation.
The applicability of static data flow architectures to the iterative solution of sparse linear systems of equations is investigated. An analytic performance model of a static data flow computation is developed. This m...
详细信息
The applicability of static data flow architectures to the iterative solution of sparse linear systems of equations is investigated. An analytic performance model of a static data flow computation is developed. This model includes both spatial parallelism, concurrent execution in multiple PEs, and pipelining, the streaming of data from array memories through the PEs. The performance model is used to analyze a row-partitioned iterative algorithms for solving sparse linear systems of algebraic equations. On the basis of this analysis, design parameters for the static data flow architecture as a function of matrix sparsity and dimension are proposed.
Consider a polynomial f with an arbitrary but xed number of variables with integral coefcients. We present an algorithm which reduces the problem of nding the irreducible factors of f in polynomial-time in the total d...
详细信息
Consider a polynomial f with an arbitrary but xed number of variables with integral coefcients. We present an algorithm which reduces the problem of nding the irreducible factors of f in polynomial-time in the total degree of f the coefcient lengths of f to factoring a univariate integral polynomial. Together with A. Lenstra s, H. Lenstra s L. Lov asz polynomial-time factorization algorithm for univariate integral polynomials this algorithm implies the following theorem. Factoring an integral polynomial with a xed number of variables into irreducibles, except for the constant factors, can be accomplished in deterministic polynomial-time in the total degree the size of its coefcients. Our algo- rithm can be generalized to factoring multivariate polynomials with coefcients in algebraic number elds nite elds in polynomial-time. We also present a different algorithm, based on an effective version of a Hilbert Irreducibility Theorem, which polynomial-time reduces testing multivariate polynomials for irreducibility to testing bivariate integral polyno- mials for irreducibility.
The well-known towers of Hanoi puzzle consists of a set of n disks of unequal size threaded onto 3 needles such that no disk rests on a smaller one. A legal move consists of removing a top disk from one needle and tr...
详细信息
The well-known towers of Hanoi puzzle consists of a set of n disks of unequal size threaded onto 3 needles such that no disk rests on a smaller one. A legal move consists of removing a top disk from one needle and transferring it to another without violating the above rule. All recursive and iterative algorithms for the problem assume that the puzzle is initially in the stack-configuration and perform the unique minimal sequence of moves to reach the final state. However, a person attempting to solve the puzzle may execute a different sequence of legal moves and leave the puzzle unfinished with any arrangement of the disks. If such an arrangement is one of the configurations of the minimal sequence of moves, someone else can finish the puzzle applying the minimal algorithm. Walsh (1982) has given a rule for identifying such cases. If the arrangement is not an intermediate configuration of the minimal sequence, this rule can recognize the error but cannot correct it.
暂无评论