Eigenvector-free solutions to AX = B with PX = XP and X = sX constraints

The matrix equation AX = B with PX = XP and X^H = sX constraints is considered, where P is a given Hermitian involutory matrix and s = ±1. By an eigenvalue decomposition of P, we equivalently transform the constrained problem to two well-known constrained problems and represent the solutions in terms of the eigenvectors of P. Using Moore-Penrose generalized inverses of the products generated by matrices A, B and P, the involved eigenvectors can be released and eigenvector-free formulas of the general solutions are presented. Similar strategy is applied to the equations AX = B, XC = D with the same constraints.     

LSQR iterative common symmetric solutions to matrix equations AXB = E and CXD = F

A new matrix based iterative method is presented to compute common symmetric solution or common symmetric least-squares solution of the pair of matrix equations AXB = E and CXD = F. By this iterative method, for any initial matrix X₀, a solution X^∗ can be obtained within finite iteration steps if exact arithmetic was used, and the solution X^∗ with the minimum Frobenius norm can be obtained by choosing a special kind of initial matrix. In addition, the unique nearest common symmetric solution or common symmetric least-squares solution to given matrix in Frobenius norm can be obtained by first finding the minimum Frobenius norm common symmetric solution or common symmetric least-squares solution of the new pair of matrix equations. The given numerical examples show that the matrix based iterative method proposed in this paper has faster convergence than the iterative methods proposed in [1] and [2] to solve the same problems.     

An O(T) algorithm for the capacitated lot sizing problem with minimum order quantities

This paper explores a single-item capacitated lot sizing problem with minimum order quantity, which plays the role of minor set-up cost. We work out the necessary and sufficient solvability conditions and apply the general dynamic programming technique to develop an O(T³) exact algorithm that is based on the concept of minimal sub-problems. An investigation of the properties of the optimal solution structure allows us to construct explicit solutions to the obtained sub-problems and prove their optimality. In this way, we reduce the complexity of the algorithm considerably and confirm its efficiency in an extensive computational study.     

An algorithm for mean residual life computation of (n − k + 1)-out-of-n systems: An application of exponentiated Weibull distribution

In this paper, we establish an algorithm for the computation of the mean residual life of a (n − k + 1)-out-of-n system in the case of independent but not necessarily identically distributed lifetimes of the components. An application for the exponentiated Weibull distribution is given to study the effect of various parameters on the mean residual life of the system. Also the relationship between the mean residual life for the system and that of its components is investigated.     

Least-squares solutions to the matrix equations AX = B and XC = D

The least-squares solution and the least-squares symmetric solution with the minimum-norm of the matrix equations AX = B and XC = D are considered in this paper. By the matrix differentiation and the spectral decomposition of matrices, an explicit representation of such solution is given.     

Computational results of an O(n) volume algorithm

Recently an O^∗(n⁴) volume algorithm has been presented for convex bodies by Lovász and Vempala, where n is the number of dimensions of the convex body. Essentially the algorithm is a series of Monte Carlo integrations. In this paper we describe a computer implementation of the volume algorithm, where we improved the computational aspects of the original algorithm by adding variance decreasing modifications: a stratified sampling strategy, double point integration and orthonormalised estimators. Formulas and methodology were developed so that the errors in each phase of the algorithm can be controlled. Some computational results for convex bodies in dimensions ranging from 2 to 10 are presented as well.     

Simplicial algorithm to solve the nonlinear complementarity problem onS n×R + m

In this paper, a simplicial algorithm is developed to solve the nonlinear complementarity problem onS ⁿ×R ₊ ^m . Furthermore, a condition for convergence is formulated. The triangulation which underlies the algorithm is a combination of the V-triangulation ofS ⁿ and the K-triangulation ofR ₊ ^m . Therefore, we will call it the VK-triangulation.The author wishes to thank Professor G. van der Laan for his valuable comments.     

Network simplex algorithm for the general equal flow problem

In this paper the general equal flow problem is considered. This is a minimum cost network flow problem with additional side constraints requiring the flow of arcs in some given sets of arcs to take on the same value. This model can be applied to approach water resource system management problems or multiperiod logistic problems in general involving policy restrictions which require some arcs to carry the same amount of flow through the given study period. Although the bases of the general equal flow problem are no longer spanning trees, it is possible to recognize a similar structure that allows us to take advantage of the practical computational capabilities of network models. After characterizing the bases of the problem as good (r+1)-forests, a simplex primal algorithm is developed that exploits the network structure of the problem and requires only slight modifications of the well-known network simplex algorithm.     

An adaptive insertion algorithm for the single-vehicle dial-a-ride problem with narrow time windows

The dial-a-ride problem (DARP) is a widely studied theoretical challenge related to dispatching vehicles in demand-responsive transport services, in which customers contact a vehicle operator requesting to be carried from specified origins to specified destinations. An important subproblem arising in dynamic dial-a-ride services can be identified as the single-vehicle DARP, in which the goal is to determine the optimal route for a single vehicle with respect to a generalized objective function. The main result of this work is an adaptive insertion algorithm capable of producing optimal solutions for a time constrained version of this problem, which was first studied by Psaraftis in the early 1980s. The complexity of the algorithm is analyzed and evaluated by means of computational experiments, implying that a significant advantage of the proposed method can be identified as the possibility of controlling computational work smoothly, making the algorithm applicable to any problem size.     

The common Re-nnd and Re-pd solutions to the matrix equations AX = C and XB = D

In this article, we consider common Re-nnd and Re-pd solutions of the matrix equations AX = C and XB = D with respect to X, where A, B, C and D are given matrices. We give necessary and sufficient conditions for the existence of common Re-nnd and Re-pd solutions to the pair of the matrix equations and derive a representation of the common Re-nnd and Re-pd solutions to these two equations when they exist. The presented examples show the advantage of the proposed approach.     

On two perturbation estimates of the extreme solutions to the equations X ± A*XA = Q

Two perturbation estimates for maximal positive definite solutions of equations X + A*X⁻¹A = Q and X − A*X⁻¹A = Q are considered. These estimates are proved in [Hasanov et al., Improved perturbation Estimates for the Matrix Equations X ± A*X⁻¹A = Q, Linear Algebra Appl. 379 (2004) 113-135]. We derive new perturbation estimates under weaker restrictions on coefficient matrices of the equations. The theoretical results are illustrated by numerical examples.     

Speeding up the Floyd-Warshall algorithm for the cycled shortest path problem

On a network with a cycle, where at least one cycle exists, the Floyd-Warshall algorithm is one of the algorithms most used for determining the least cost path between every pair of nodes. In this work a new algorithm for this problem is developed that requires less computational effort than the Floyd-Warshall algorithm. Furthermore, we show that the basis of our algorithm is much easier to understand, which might be an advantage for educational purposes. A small example validates our algorithm and shows its implementation.     

A branch-and-bound algorithm to solve the linear ordering problem for weighted tournaments

The linear ordering problem consists in finding a linear order at minimum remoteness from a weighted tournament T, the remoteness being the sum of the weights of the arcs that we must reverse in T to transform it into a linear order. This problem, also known as the search of a median order, or of a maximum acyclic subdigraph, or of a maximum consistent set, or of a minimum feedback arc set, is NP-hard; when all the weights of T are equal to 1, the linear ordering problem is the same as Slater's problem. In this paper, we describe the principles and the results of an exact method designed to solve the linear ordering problem for any weighted tournament. This method, of which the corresponding software is freely available at the URL address http://www.enst.fr/~charon/tournament/median.html, is based upon a branch-and-bound search with a Lagrangean relaxation as the evaluation function and a noising method for computing the initial bound. Other components are designed to reduce the BB-search-tree.     

A non-interior continuation algorithm for solving the convex feasibility problem

In this paper, a specific class of convex feasibility problems are considered and a non-interior continuation algorithm based on a smoothing function to solve this class of problems is introduced. The proposed algorithm solves at most one system of linear equations at each iteration. Under some weak assumptions, we show that the algorithm is globally linearly and locally quadratically convergent. Preliminary numerical results are also reported, which verify the favorable theoretical properties of the proposed algorithm.     

Inequalities between ∥f(A + B)∥ and ∥f(A) + f(B)∥

The conjecture posed by Aujla and Silva [J.S. Aujla, F.C. Silva, Weak majorization inequalities and convex functions, Linear Algebra Appl. 369 (2003) 217-233] is proved. It is shown that for any m-tuple of positive-semidefinite n × n complex matrices A_j and for any non-negative convex function f on [0, ∞) with f(0) = 0 the inequality ?f(A₁) + f(A₂) + ? + f(A_m)? ? ? f(A₁ + A₂ + ? + A_m)? holds for any unitarily invariant norm ? · ?. It is also proved that ?f(A₁) + f(A₂) + ? + f(A_m)? ? f(?A₁ + A₂ + ? + A_m?), where f is a non-negative concave function on [0, ∞) and ? · ? is normalized.     

An O(n2log n) parallel max-flow algorithm

A synchronized parallel algorithm for finding maximum flow in a directed flow network is presented. Its depth is $\text{O(}\text{n}{}^3\text{(}\text{log}\text{n)}\text{p)}$, where p (p ≤ n) is the number of processors used. This problem seems to be more involved than most of the problems for which efficient parallel algorithms exist. The parallel algorithm induces a new rather simple sequential O(n³) algorithm. This algorithm is very much parallel oriented. It is quite difficult to conceive and analyze it, if one is restricted to the sequential point of view.     

An edge-reduction algorithm for the vertex cover problem

An approximation algorithm for the vertex cover problem is proposed with performance ratio on special graphs. On an arbitrary graph, the algorithm guarantees a vertex cover S₁ such that where S^∗ is an optimal cover and ξ is an error bound identified.