A Dual Framework for Lower Bounds of the Quadratic Assignment Problem Based on Linearization

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     

Semi On-Line Scheduling on Two Identical Machines

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     

Complexity Results for Single-Machine Problems with Positive Finish-Start Time-Lags

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     

A New Multisection Technique in Interval Methods for Global Optimization

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     

Computation of Lagrange Multipliers for Linear Least Squares Problems with Equality Constraints

Received December 21, 2000; revised June 7, 2001     

Dynamic Programming Revisited: Improving Knapsack Algorithms

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     

Acquisition of Complex Model Knowledge by Domain Theory-Controlled Generalization

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     

Simulated Annealing for Fitting Linear Combinations of Gaussians to Data

 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     

A Numerical Method to Verify the Elliptic Eigenvalue Problems Including a Uniqueness Property

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     

Scheduling a Single Server in a Two-machine Flow Shop

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 ³) time when all job processing times on the first machine are equal, and it is solved in O(n ⁴) time when all processing times on the second machine are equal. Received November 20, 2001; revised October 18, 2002 Published online: January 16, 2003     

Global Convergence of a Class of Collinear Scaling Algorithms with Inexact Line Searches on Convex Functions

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     

A Class of Smoothers for Saddle Point Problems

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     

On the Stability of the Direct Elimination Method for Equality Constrained Least Squares Problems

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     

Volume Maximization and Orthoconvex Approximation of Orthogons

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     

On the Convergence Rate of a Preconditioned Subspace Eigensolver

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     

Iterative Methods for Linear Complementarity Problems with Interval Data

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.     

Descent Iterations for Improving Approximate Eigenpairs of Polynomial Eigenvalue Problems with General Complex Matrices

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     

More About Subcolorings

A subcoloring is a vertex coloring of a graph in which every color class induces a disjoint union of cliques. We derive a number of results on the combinatorics, the algorithmics, and the complexity of subcolorings. On the negative side, we prove that 2-subcoloring is NP-hard for comparability graphs, and that 3-subcoloring is NP-hard for AT-free graphs and for complements of planar graphs. On the positive side, we derive polynomial time algorithms for 2-subcoloring of complements of planar graphs, and for r-subcoloring of interval and of permutation graphs. Moreover, we prove asymptotically best possible upper bounds on the subchromatic number of interval graphs, chordal graphs, and permutation graphs in terms of the number of vertices. Received June 11, 2002; revised September 13, 2002 Published online: November 25, 2002 RID="*" ID="*" The work of HJB and FVF is sponsored by NWO-grant 047.008.006. FVF acknowledges support by EC contract IST-1999-14186, Project ALCOM-FT (Algorithms and Complexity – Future Technologies). Part of this work was done while FVF was visiting the University of Twente, and while he was a visiting postdoc at DIMATIA-ITI (supported by GAČR 201/99/0242 and by the Ministry of Education of the Czech Republic as project LN00A056). JN acknowledges support of ITI – the Project LN00A056 of the Czech Ministery of Education. GJW acknowledges support by the START program Y43-MAT of the Austrian Ministry of Science.