A branch and bound algorithm for the robust shortest path problem with interval data

Many real problems can be modelled as robust shortest path problems on interval digraphs, where intervals represent uncertainty about real costs and a robust path is not too far from the shortest path for each possible configuration of the arc costs.A branch and bound algorithm for this problem is presented.     

A note on worst-case performance of heuristics for maintenance scheduling problems

We study a machine scheduling model in which job scheduling and machine maintenance activities have to be considered simultaneously. We develop the worst-case bounds for some heuristic algorithms, including a sharper worst-case bound of the SPT schedule than the results in the literature, and another bound of the EDD schedule.     

Lower bound for the convergence rate of nonstationary Jacobi-like iteration

Stationary and nonstationary Jacobi-like iterative processes for solving systems of linear algebraic equations are examined. For a system whose coefficient matrix A is an H-matrix, it is shown that the convergence rate of any Jacobi-like process is at least as high as that of the point Jacobi method as applied to a system with 〈A〉 as the coefficient matrix, where 〈A〉 is a comparison matrix of A.     

An improved max-flow-based lower bound for minimizing maximum lateness on identical parallel machines

In this paper, we introduce a new concept of semi-preemptive scheduling and we show how it can be used to derive a maximum-flow-based lower bound for the P|r_j|L_max which dominates the well-known preemptive lower bound. We show that, in some cases, the proposed bound strictly dominates the preemptive one while having the same complexity.     

A lower bound on the performance of the quadratic discriminant function

The quadratic discriminant function is often used to separate two classes of points in a multidimensional space. When the two classes are normally distributed, this results in the optimum separation. In some cases however, the assumption of normality is a poor one and the classification error is increased. The current paper derives an upper bound for the classification error due to a quadratic decision surface. The bound is strict when the class means and covariances and the quadratic discriminant surface satisfy certain specified symmetry conditions.     

A two-stage parallel branch and bound algorithm for mixed integer programs

Mixed integer programming (MIP) models are extensively usedto aid strategic and tactical decision making in many businesssectors. Solving MIP models is a computationally intensive processand there is a need to develop solution approaches that enablelarger models to be solved within acceptable timeframes. Inthis paper, we describe the implementation of a two-stage parallelbranch and bound (PB & B) algorithm for MIP. In stage 1of the algorithm, a multiple heuristic search is implementedin which a number of alternative search trees are investigatedusing a forest search in the hope of finding a good solutionquickly. In stage 2, the search is reorganized so that the branchesof a chosen tree are investigated in parallel. A new heuristicis introduced, based on a best projection criterion, which evaluatesalternative B & B trees in order to choose one for investigationin stage 2 of the algorithm. The heuristic also serves as away of implementing a quality load balancing scheme for stage2 of the algorithm. The results of experimental investigationsare reported for a range of models taken from the MIPLIB libraryof benchmark problems.     

Randomization helps to perform independent tasks reliably

This paper is about algorithms that schedule tasks to be performed in a distributed failure‐prone environment, when processors communicate by message‐passing, and when tasks are independent and of unit length. The processors work under synchrony and may fail by crashing. Failure patterns are imposed by adversaries. Linearly‐bounded adversaries may fail up to a constant fraction of the processors. Weakly‐adaptive adversaries have to select, prior to the start of an execution, a subset of processors to be failure‐prone, and then may fail only the selected processors, at arbitrary steps, in the course of the execution. Strongly adaptive adversaries have a total number of failures as the only restriction on failure patterns. The measures of complexity are work, measured as the available processor steps, and communication, measured as the number of point‐to‐point messages. A randomized algorithm is developed, that attains both ??(n log*n) expected work and ??(n log*n) expected communication, against weakly‐adaptive linearly‐bounded adversaries, in the case when the numbers of tasks and processors are both equal to n. This is in contrast with performance of algorithms against strongly‐adaptive linearly‐bounded adversaries, which has to be Ω(n log n/log log n) in terms of work. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 2004     

Practical algorithms for transposition-invariant string-matching

We consider the problems of (1) longest common subsequence (LCS) of two given strings in the case where the first may be shifted by some constant (that is, transposed) to match the second, and (2) transposition-invariant text searching using indel distance. These problems have applications in music comparison and retrieval. We introduce two novel techniques to solve these problems efficiently. The first is based on the branch and bound method, the second on bit-parallelism. Our branch and bound algorithm computes the longest common transposition-invariant subsequence (LCTS) in time O((m²+loglogσ)logσ) in the best case and O((m²+logσ)σ) in the worst case, where m and σ, respectively, are the length of the strings and the size of the alphabet. On the other hand, we show that the same problem can be solved by using bit-parallelism and thus obtain a speedup of O(w/logm) over the classical algorithms, where the computer word has w bits. The advantage of this latter algorithm over the present bit-parallel ones is that it allows the use of more complex distances, including general integer weights. Since our branch and bound method is very flexible, it can be further improved by combining it with other efficient algorithms such as our novel bit-parallel algorithm. We experiment on several combination possibilities and discuss which are the best settings for each of those combinations. Our algorithms are easily extended to other musically relevant cases, such as δ-matching and polyphony (where there are several parallel texts to be considered). We also show how our bit-parallel algorithm is adapted to text searching and illustrate its effectiveness in complex cases where the only known competing method is the use of brute force.     

On perturbations of matrix pencils with real spectra, a revisit

This paper continues earlier studies by Bhatia and Li on eigenvalue perturbation theory for diagonalizable matrix pencils having real spectra. A unifying framework for creating crucial perturbation equations is developed. With the help of a recent result on generalized commutators involving unitary matrices, new and much sharper bounds are obtained.

     

Regularity of Harmonic Functions in Cheeger-Type Sobolev Spaces

We give a geometric approach to the study of the regularity of harmonic functions in Cheeger-type Sobolev spaces, and prove the Hölder continuity of such functions. In the proof, we give a definition of an upper curvature bound of the unit sphere of a Banach space, which seems to be of independent interest.