共查询到20条相似文献,搜索用时 15 毫秒
1.
Interval arithmetic can be used to enclose the range of a real function over a domain. However, due to some weak properties
of interval arithmetic, a computed interval can be much larger than the exact range. This phenomenon is called dependency
problem. In this paper, Horner's rule for polynomial interval evaluation is revisited. We introduce a new factorization scheme
based on well-known symbolic identities in order to handle the dependency problem of interval arithmetic. The experimental
results show an improvement of 25% of the width of computed intervals with respect to Horner's rule.
Received December 14, 2001; revised March 27, 2002 Published online: July 8, 2002 相似文献
2.
Semi On-Line Scheduling on Two Identical Machines 总被引:29,自引:0,他引:29
This paper investigates two different semi on-line scheduling problems on a two-machine system. In the first case, we assume
that all jobs have their processing times in between p and rp
. In the second case, we assume that the largest processing time is known in advance. We show that one has a best possible
algorithm with worst case ratio 4/3 while LS is still the best possible for the other problem with ratio which is still in the worst case .
Received: February 23, 1998; revised August 5, 1998 相似文献
3.
Cs. Imreh 《Computing》2001,66(3):289-296
A manufacturing system consists of operating units which convert their input materials into their output materials. In the
problem of designing a process network, we have to find a suitable network of operating units which produces the desired products
from the given raw materials. If we consider this process network design problem from a structural point of view, then we
obtain a combinatorial optimization problem called the Process Network Synthesis or (PNS) problem. It is known that the PNS
problem is NP-complete. Here, a new method is presented to reduce the solution of some more difficult PNS problems to the
solution of simpler ones, and using this method, a new well-solvable class of PNS problems is established.
Received February 12, 1999; revised October 24, 2000 相似文献
4.
Ariyawansa [2] has presented a class of collinear scaling algorithms for unconstrained minimization. A certain family of algorithms
contained in this class may be considered as an extension of quasi-Newton methods with the Broyden family [11] of approximants
of the objective function Hessian. Byrd, Nocedal and Yuan [7] have shown that all members except the DFP [11] method of the
Broyden convex family of quasi-Newton methods with Armijo [1] and Goldstein [12] line search termination criteria are globally
and q-superlinearly convergent on uniformly convex functions. Extension of this result to the above class of collinear scaling
algorithms of Ariyawansa [2] has been impossible because line search termination criteria for collinear scaling algorithms
were not known until recently. Ariyawansa [4] has recently proposed such line search termination criteria. In this paper,
we prove an analogue of the result of Byrd, Nocedal and Yuan [7] for the family of collinear scaling algorithms of Ariyawansa
[2] with the line search termination criteria of Ariyawansa [4].
Received: May 8, 1996; revised January 27, 1999 相似文献
5.
Scheduling a Single Server in a Two-machine Flow Shop 总被引:1,自引:0,他引:1
We study the problem of scheduling a single server that processes n jobs in a two-machine flow shop environment. A machine dependent setup time is needed whenever the server switches from one
machine to the other. The problem with a given job sequence is shown to be reducible to a single machine batching problem.
This result enables several cases of the server scheduling problem to be solved in O(n log n) by known algorithms, namely, finding a schedule feasible with respect to a given set of deadlines, minimizing the maximum
lateness and, if the job processing times are agreeable, minimizing the total completion time. Minimizing the total weighted
completion time is shown to be NP-hard in the strong sense. Two pseudopolynomial dynamic programming algorithms are presented
for minimizing the weighted number of late jobs. Minimizing the number of late jobs is proved to be NP-hard even if setup
times are equal and there are two distinct due dates. This problem is solved in O(n
3) time when all job processing times on the first machine are equal, and it is solved in O(n
4) time when all processing times on the second machine are equal.
Received November 20, 2001; revised October 18, 2002
Published online: January 16, 2003 相似文献
6.
In a single-machine problem with time-lags a set of jobs has to be processed on a single machine in such a way that certain
timing restrictions between the finishing and starting times of the jobs are satisfied and a given objective function is minimized.
We consider the case of positive finish-start time-lags which mean that between the finishing time of job i and the starting time of job j the minimal distance has to be respected. New complexity results are derived for single-machine problems with constant positive time-lags which also lead to new results for flow-shop problems with unit processing times and job precedences.
Received: May 13, 1998; revised November 23, 1998 相似文献
7.
This paper presents an easy and straightforward routing algorithm for WK-recursive topologies. The algorithm, based on adaptive
routing, takes advantage of the geometric properties of such topologies. Once a source node S and destination node D have
been determined for a message communication, they characterize, at some level l, two virtual nodes and that respectively contain S but not D and D but not S. Such virtual nodes characterize other (where is the node degree for a fixed topology) virtual nodes of the same level that contain neither S nor D. Consequently, it is possible to locate triangles whose vertices are these virtual nodes with property to share the same path, called the self-routing path, directly connecting to . When the self-routing path is unavailable to transmit a message from S to D because of deadlock, fault, and congestion conditions,
the routing strategy can follow what we call the triangle rule to deliver it. The proposed communication scheme has the advantage that 1) it is the same for all three conditions; 2) each
node of a WK-recursive network, to transmit messages, does not require any information about their presence or location. Furthermore,
this routing algorithm is able to tolerate up to faulty links.
Received: July 19, 1998; revised May 17, 1999 相似文献
8.
A dual framework allowing the comparison of various bounds for the quadratic assignment problem (QAP) based on linearization,
e.g. the bounds of Adams and Johnson, Carraresi and Malucelli, and Hahn and Grant, is presented. We discuss the differences
of these bounds and propose a new and more general bounding procedure based on the dual of the linearization of Adams and
Johnson. The new procedure has been applied to problems of dimension up to , and the computational results indicate that the new bound competes well with existing linearization bounds and yields a
good trade off between computation time and bound quality.
Received: February 5, 1999; revised August 24, 1999 相似文献
9.
R. Englert 《Computing》1999,62(4):369-385
Nearly all three-dimensional reconstruction methods lack proper model knowledge that reflects the scene. Model knowledge is
required in order to reduce ambiguities which occur during the reconstruction process. It must comprise the scene and is therefore
complex, and additionally difficult to acquire. In this paper we present an approach for the learning of complex model knowledge.
A (large) sample set of three-dimensionally acquired buildings represented as graphs is generalized by the use of background
knowledge. The background knowledge entails domain-specific knowledge and is utilized for the search guidance during the generalization
process of EXRES. The generalization result is a distribution of relevant patterns which reduces ambiguities occurring in
3D object reconstruction (here: buildings). Three different applications for the 3D reconstruction of buildings from aerial
images are executed whereas binary relations of so-called building atoms, namely tertiary nodes and faces, and building models are learned. These applications are evaluated based on (a) the estimated
empirical generalization error and (b) the use of information coding theory and statistics by comparing the learned knowledge
with non-available a priori knowledge.
Received: June 3, 1998; revised November 5, 1998 相似文献
10.
Received December 21, 2000; revised June 7, 2001 相似文献
11.
A new multisection technique in interval methods for global optimization is investigated, and numerical tests demonstrate
that the efficiency of the underlying global optimization method can be improved substantially. The heuristic rule is based
on experiences that suggest the subdivision of the current subinterval into a larger number of pieces only if it is located
in the neighbourhood of a minimizer point. An estimator of the proximity of a subinterval to the region of attraction to a
minimizer point is utilized. According to the numerical study made, the new multisection strategies seem to be indispensable,
and can improve both the computational and the memory complexity substantially.
Received May 31, 1999; revised January 20, 2000 相似文献
12.
K. Ishihara 《Computing》2002,68(3):239-254
In this paper, we consider descent iterations with line search for improving an approximate eigenvalue and a corresponding
approximate eigenvector of polynomial eigenvalue problems with general complex matrices, where an approximate eigenpair was
obtained by some method. The polynomial eigenvalue problem is written as a system of complex nonlinear equations with nondifferentiable
normalized condition. Convergence theorems for iterations are established. Finally, some numerical examples are presented
to demonstrate the effectiveness of the iterative methods.
Received April 9, 2001; revised October 2, 2001 Published online February 18, 2002 相似文献
13.
A new method for lossless image compression of grey-level images is proposed. The image is treated as a set of stacked bit
planes. The compressed version of the image is represented by residuals of a non-linear local predictor spanning the current
bit plane as well as a few neighbouring ones. Predictor configurations are grouped in pairs differing in one bit of the representative
point only. The frequency of predictor configurations is obtained from the input image. The predictor adapts automatically
to the image, it is able to estimate the influence of neighbouring cells and thus copes even with complicated structure or
fine texture.
The residuals between the original and the predicted image are those that correspond to the less frequent predictor configurations.
Efficiently coded residuals constitute the output image. To our knowledge, the performance of the proposed compression algorithm
is comparable to the current state of the art. Especially good results were obtained for binary images, grey-level cartoons
and man-made drawings.
Received: June 29, 1998; revised November 2, 1998 相似文献
14.
We propose a modification of Newton's method for computing multiple roots of systems of analytic equations. Under mild assumptions
the iteration converges quadratically. It involves certain constants whose product is a lower bound for the multiplicity of
the root. As these constants are usually not known in advance, we devise an iteration in which not only an approximation for
the root is refined, but also approximations for these constants. Numerical examples illustrate the effectiveness of our approach.
Received: August 17, 1998 相似文献
15.
The paper is concerned with solving the periodically perturbed nonconservative systems, which will be differentiably imbedded
into an one-parameter family of operators. The solution of the systems is then found by continuing the solution curve of operator
homotopy. When the Newton-Kantorovich's procedure is applied to the corresponding operator equations, an efficient algorithm
is derived. Furthermore, the suitable condition on the optimum step size of the parameter is provided for assuring that the
approximation solution will converge to the unique solution of the nonlinear periodically boundary value problem. Finally,
the theoretical results are in excellent agreement with the numerical examples.
Received August 14, 2001; revised December 19, 2001 Published online: November 18, 2002 相似文献
16.
J. R. Parker 《Computing》2000,65(4):291-312
It is difficult to find a good fit of a combination of Gaussians to arbitrary empirical data. The surface defined by the
objective function contains many local minima, which trap gradient descent algorithms and cause stochastic methods to tarry
unreasonably in the vicinity. A number of techniques for accelerating convergence when using simulated annealing are presented.
These are tested on a sample of known Gaussian combinations and are compared for accuracy and resource consumption. A single
`best' set of techniques is found which gives good results on the test samples and on empirical data.
Received September 27, 1999; revised March 13, 2000 相似文献
17.
18.
For factoring a positive integer n into primes, four variants of the elementary algorithm are analysed. The worst-case time complexities vary from Θ() up to Θ(). The average time complexities vary from Θ() up to Θ().
Received August 21, 1998; revised September 14, 2000 相似文献
19.
This paper presents a system for automatically selecting images in an image database to be used as illustrations of an image
method or analysis process. This problem is related to the teleteaching of image processing which uses already implemented
libraries of algorithms. This is in the context of a teleteaching European project. We first give a Bayesian approach to this
problem, by using an image basis. Then we show how to use the Haar transform for this purpose. Finally we give examples and
discuss our approach.
Received: June 8, 1998; revised December 17, 1998 相似文献
20.
We consider the preemptive job shop scheduling problem with two machines, with the objective to minimize the makespan. We
present an algorithm that finds a schedule of length at most P
max/2 greater than the optimal schedule length, where P
max is the length of the longest job.
Received June 13, 2000 相似文献