共查询到20条相似文献,搜索用时 0 毫秒
1.
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 相似文献
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.
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 相似文献
4.
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 相似文献
5.
Received December 21, 2000; revised June 7, 2001 相似文献
6.
Dynamic Programming Revisited: Improving Knapsack Algorithms 总被引:1,自引:1,他引:0
U. Pferschy 《Computing》1999,63(4):419-430
The contribution of this paper is twofold: At first an improved dynamic programming algorithm for the bounded knapsack problem
is given. It decreases the running time for an instance with n items and capacity c from to , which is the same pseudopolynomial complexity as usually given for the 0--1 knapsack problem. In the second part a general
approach based on dynamic programming is presented to reduce the storage requirements for combinatorial optimization problems
where it is computationally more expensive to compute the explicit solution structure than the optimal solution value. Among
other applications of this scheme it is shown that the 0--1 knapsack problem as well as the bounded knapsack problem can be
solved in time and space.
Received: October 15, 1998; revised March 10, 1999 相似文献
7.
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 相似文献
8.
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 相似文献
9.
K. Nagatou 《Computing》1999,63(2):109-130
We propose a numerical method to enclose the eigenvalues and eigenfunctions of second-order elliptic operators with local
uniqueness. We numerically construct a set containing eigenpairs which satisfies the hypothesis of Banach's fixed point theorem in a certain Sobolev space by using a finite element approximation
and constructive error estimates. We then prove the local uniqueness separately of eigenvalues and eigenfunctions. This local uniqueness assures the simplicity of the eigenvalue. Numerical examples are
presented.
Received: November 2, 1998; revised June 5, 1999 相似文献
10.
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 相似文献
11.
Walter Zulehner 《Computing》2000,65(3):227-246
In this paper smoothing properties are shown for a class of iterative methods for saddle point problems with smoothing rates
of the order 1/m, where m is the number of smoothing steps. This generalizes recent results by Braess and Sarazin, who could prove this rates for methods
where, in the context of the Stokes problem, the pressure correction equation is solved exactly, which is not needed here.
Received December 4, 1998; revised April 14, 2000 相似文献
12.
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 相似文献
13.
A backward error analysis of the direct elimination method for linear equality constrained least squares problems is presented.
It is proved that the solution computed by the method is the exact solution of a perturbed problem and bounds for data perturbations
are given. The numerical stability of the method is related to the way in which the constraints are used to eliminate variables
and these theoretical conclusions are confirmed by a numerical example.
Received February 15, 1999; revised December 10, 1999 相似文献
14.
On the Convergence Rate of a Preconditioned Subspace Eigensolver 总被引:1,自引:0,他引:1
S. Oliveira 《Computing》1999,63(3):219-231
In this paper we present a proof of convergence for a preconditioned subspace method which shows the dependency of the convergence
rate on the preconditioner used. This convergence rate depends only on the condition of the pre-conditioned system and the relative separation of the first two eigenvalues . This means that, for example, multigrid preconditioners can be used to find eigenvalues of elliptic PDE's at a grid-independent
rate.
Received: March 9, 1999, revised June 23, 1999 相似文献
15.
Claudio Canuto 《Computing》2001,66(2):121-138
We are concerned with the task of stabilizing discrete approximations to convection–diffusion problems. We propose to consistently
modify the exact variational formulation of the problem by adding a fractional order inner product, involving the residual
of the equation. The inner product is expressed through a multilevel decomposition of its arguments, in terms of components
along a multiscale basis. The order of the inner product locally varies from −1/2 to −1, depending on the value of a suitably-defined
multiscale Péclet number. Numerical approximations obtained via the Galerkin method applied to the modified formulation are
analyzed.
Received January 1, 2000; revised November 2, 2000 相似文献
16.
Let n axes-parallel hyperparallelepipeds (also called blocks) of the d-dimensional Euclidean space and a positive integer r be given. The volume maximization problem (VMP) selects at most r blocks such that the volume of their union becomes maximum. VMP is shown to be -hard in the 2-dimensional case and polynomially solvable for the line via a constrained critical path problem (CCPP) in an
acyclic digraph. This CCPP leads to further well solvable special cases of the maximization problem. In particular, the following
approximation problem (OAP) becomes polynomially solvable: given an orthogon P (i.e., a simple polygon in the plane which is a union of blocks) and a positive integer q, find an orthoconvex orthogon with at most q vertices and minimum area, which contains P.
Received: September 7, 1998 相似文献
17.
A ] and an interval vector [b]. If all A∈[A] are H-matrices with positive diagonal elements, these methods are all convergent to the same interval vector [x
*]. This interval vector includes the solution x of the linear complementarity problem defined by any fixed A∈[A] and any fixed b∈[b]. If all A∈[A] are M-matrices, then we will show, that [x
*] is optimal in a precisely defined sense. We also consider modifications of those methods, which under certain assumptions
on the starting vector deliver nested sequences converging to [x
*]. We close our paper with some examples which illustrate our theoretical results.
Received October 7, 2002; revised April 15, 2003
Published online: June 23, 2003
RID="*"
ID="*" Dedicated to U. Kulisch on the occasion of his 70th birthday.
We are grateful to the referee who has given a series of valuable comments. 相似文献
18.
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 相似文献
19.