Further results on the algebraic characterizations of a minimum cost network flow problem equivalent to the transportation problem

In this study a minimum cost network flow problem with m+n+2 nodes and mn arcs, which is equivalent to the transportation problem with m sources and n destinations, is described as an axial four-index transportation problem of order 1×m×n×1. Several algebraic characterizations of this problem of order 1×m×n×1 are investigated using the singular value decomposition and generalized inverses of its coefficient matrix. The results are compared with some results on the planar four-index transportation problem. It is shown that these problems have common algebraic characterizations and can be solved in terms of eigenvectors of the matrices J _m and J _n where J _m is an m×m matrix, all of whose entries are 1.     

Some new results on the algebraic characterizations of an equality constrained optimization problem equivalent to the transportation problem

An equality constrained optimization problem equivalent to the transportation problem with m sources and n destinations is described. The optimality condition and some algebraic characterizations of the problem are investigated using its Hessian matrix. In addition, several algebraic characterizations of an equivalent case of the transportation problem are given using the spectral decomposition and generalized inverses of its coefficient matrix. It is shown that the transportation problem and its equivalent case have common algebraic characterizations.     

Improving loops and vanishing variables in long transportation problems

In this paper the following two results are presented: (1)A method which determines the optimal values of certain variables during the iterative solution process. The closer the current primal feasible solution is to the optimal solution, the greater the number of variables which may be determined. (2) For each current feasible solution (X_ij) of the given m × n transportation problem A, a feasible solution ($\text{X}\text{?}{}_{\mathrm{ij}}$) of an auxiliary m × m(m ?1) transportation problem $\text{A}\text{?}$ is constructed. Problem $\text{A}\text{?}$ is shown to be equivalent to an m(m ? 1) × m(m ? 1) assignment problem with two admissible cells per column. The optimally of (X_ij) is shown to imply the optimality of ($\text{X}\text{?}{}_{\mathrm{ij}}$) and conversely. The best “improving loops” (including the improving loops used in MODI) of $\text{A}\text{?}$ are shown to be the best “improving loops” of A as well.     

Some consequences on the planar three-index transportation problem

In this study, some algebraic characterizations of the coefficient matrix A of the planar three-index transportation problem are derived and the equivalent formulation of this problem is obtained using the Kronecker product. It is shown that eigenvectors of the matrix G ⁺ G are characterized in terms of eigenvectors of the matrix A ⁺ A , where G ⁺ is the Moore–Penrose inverse of the coefficient matrix G of the equivalent problem.     

An efficient solution to the subset‐sum problem on GPU

We present an algorithm to solve the subset‐sum problem (SSP) of capacity c and n items with weights w_i,1≤i≤n, spending O(n(m − w_min)/p) time and O(n + m − w_min) space in the Concurrent Read/Concurrent Write (CRCW) PRAM model with 1≤p≤m − w_min processors, where w_min is the lowest weight and , improving both upper‐bounds. Thus, when n≤c, it is possible to solve the SSP in O(n) time in parallel environments with low memory. We also show OpenMP and CUDA implementations of this algorithm and, on Graphics Processing Unit, we obtained better performance than the best sequential and parallel algorithms known so far. Copyright © 2015 John Wiley & Sons, Ltd.     

AN ALGORITHM FOR FINDING ALL FUNCTIONS EMBEDDED IN A RELATION

The problem is posed: find an algorithm which for any given n-dimensional relation R ? A₁ × A₂ × ? × A_n, defined on a set family A = { A₁, A₂, ?, A_nrcub;, n = 1,2, ?, determines all functional dependences between disjoint subsets of A which are embedded in R. A solution algorithm is presented, a theorem is proved that allows a simplification in the algorithm, and an efficient computer implementation (available through the General Systems Depository) is demonstrated.     

Quadratic Lower Bound for Permanent Vs. Determinant in any Characteristic

In Valiant’s theory of arithmetic complexity, the classes VP and VNP are analogs of P and NP. A fundamental problem concerning these classes is the Permanent and Determinant Problem: Given a field \mathbbF{\mathbb{F}} of characteristic ≠ 2, and an integer n, what is the minimum m such that the permanent of an n × n matrix X = (x_ij) can be expressed as a determinant of an m × m matrix, where the entries of the determinant matrix are affine linear functions of x_ij ’s, and the equality is in \mathbbF[X]{\mathbb{F}}[{\bf X}]. Mignon and Ressayre (2004) proved a quadratic lower bound m = W(n²)m = \Omega(n^{2}) for fields of characteristic 0. We extend the Mignon–Ressayre quadratic lower bound to all fields of characteristic ≠ 2.     

L(2, 1)-labellings for direct products of a triangle and a cycle

An L(2, 1)-labelling of a graph G is a vertex labelling such that the difference of the labels of any two adjacent vertices is at least 2 and that of any two vertices of distance 2 is at least 1. The minimum span of all L(2, 1)-labellings of G is the λ-number of G and denoted by λ(G). Lin and Lam computed λ(G) for a direct product G=K _m ×P _n of a complete graph K _m and a path P _n . This is a natural lower bound of λ(K _m ×C _n ) for a cycle C _n . They also proved that when n≡ 0±od 5m, this bound is the exact value of λ(K _m ×C _n ) and computed the value when n=3, 5, 6. In this article, we compute the λ-number of G, where G is the direct product K ₃×C _n of the triangle and a cycle C _n for all the other n. In fact, we show that among these n, λ(K ₃×C _n )=7 for all n≠7, 11 and λ(K ₃×C _n )=8 when n=7, 11.     

Improved Controller Design for Uncertain Positive Systems and its Extension to Uncertain Positive Switched Systems

This paper is concerned with the controller design of uncertain positive systems. First, we decompose the feedback gain matrix K_m×n into m×n non‐negative components and m×n non‐positive components. For the non‐negative components, each component contains only one positive element and the other elements are zero. Similarly, each non‐positive component contains only one negative element and the other ones are zero. Then, a simple and effective controller design approach of uncertain positive systems is proposed by incorporating the decomposed feedback gain matrix into the resulting closed‐loop systems and further applied to uncertain positive switched systems. It is shown that the designed controller is less conservative compared with those in the literature. Finally, a numerical example is provided to verify the validity of the proposed design.     

An effective approach to the optimal-control problem for time-varying linear systems via Taylor series

The Taylor series is used for the solution of the optimal-control problem for time-varying linear systems. Instead of solving the state transition matrix from the state equation with a terminal condition, the present approach first transforms the terminal condition into an initial condition, and then solves the initial-value problem to find the transition matrix. This approach leads lo a recursive algebraic formulation for the transition matrix, and only an inverse matrix of small dimension 2n × 2n appears in this formulation. Thus a closed-loop control law is obtained without solving the non-linear Riccati equation, and the matrix to be inverted has only small dimension 2n × 2n. The present approach is of great interest because of its simplicity and numerical stability.     

Geometric applications of a matrix-searching algorithm

LetA be a matrix with real entries and letj(i) be the index of the leftmost column containing the maximum value in rowi ofA.A is said to bemonotone ifi ₁ >i ₂ implies thatj(i ₁) J(i ₂).A istotally monotone if all of its submatrices are monotone. We show that finding the maximum entry in each row of an arbitraryn xm monotone matrix requires (m logn) time, whereas if the matrix is totally monotone the time is (m) whenmn and is (m(1 + log(n/m))) whenm<n. The problem of finding the maximum value within each row of a totally monotone matrix arises in several geometric algorithms such as the all-farthest-neighbors problem for the vertices of a convex polygon. Previously only the property of monotonicity, not total monotonicity, had been used within these algorithms. We use the (m) bound on finding the maxima of wide totally monotone matrices to speed up these algorithms by a factor of logn.On leave from the Technion, Haifa, Israel.     

Polynomially solvable cases of the traveling salesman problem and a new exponential neighborhood

LetA=(a _ij ) be the distance matrix of an arbitrary (asymmetric) traveling salesman problem and let τ=τ₁τ₂...τ _m be the optimal solution of the corresponding assignment problem with the subtours τ=τ₁τ₂...τ _m . By choosing (m?1) transpositions (k, l) withk ∈ τ _i?1,l ∈ τ _i (i=2, ...,m) and patching the subtours by using these transpositions in any order, we get a set of cyclic permutations. It will be shown that within this set of cyclic permutations a tour with minimum distance can be found by O(n ²|τ|* operations, where |τ|* is the maximum number of nodes in a subtour of τ. Moreover, applying this result to the case whenA=(a _ij ) is a permuted distribution matrix (Monge-matrix) and thepatching graph G _τ is a multipath, a result of Gaikov can be improved: By combining the above theory with a result of Park alinear algorithm for finding an optimal TSP solution can be derived, provided τ is already known.     

Geometric applications of a matrix-searching algorithm

LetA be a matrix with real entries and letj(i) be the index of the leftmost column containing the maximum value in rowi ofA.A is said to bemonotone ifi ₁ >i ₂ implies thatj(i ₁) ≥J(i ₂).A istotally monotone if all of its submatrices are monotone. We show that finding the maximum entry in each row of an arbitraryn xm monotone matrix requires Θ(m logn) time, whereas if the matrix is totally monotone the time is Θ(m) whenm≥n and is Θ(m(1 + log(n/m))) whenm<n. The problem of finding the maximum value within each row of a totally monotone matrix arises in several geometric algorithms such as the all-farthest-neighbors problem for the vertices of a convex polygon. Previously only the property of monotonicity, not total monotonicity, had been used within these algorithms. We use the Θ(m) bound on finding the maxima of wide totally monotone matrices to speed up these algorithms by a factor of logn.     

Strong product of factor-critical graphs

Strong product G ₁? G ₂ of two graphs G ₁ and G ₂ has a vertex set V(G ₁)×V(G ₂) and two vertices (u ₁, v ₁) and (u ₂, v ₂) are adjacent whenever u ₁=u ₂ and v ₁ is adjacent to v ₂ or u ₁ is adjacent to u ₂ and v ₁=v ₂, or u ₁ is adjacent to u ₂ and v ₁ is adjacent to v ₂. We investigate the factor-criticality of G ₁? G ₂ and obtain the following. Let G ₁ and G ₂ be connected m-factor-critical and n-factor-critical graphs, respectively. Then i. if m? 0, n=0, |V(G ₁)|? 2m+2 and |V(G ₂)|? 4, then G ₁? G ₂ is (2m+2)-factor-critical;

ii. if n=1, |V(G ₁)|? 2m+3 and either m? 3 or |V(G ₂)|? 5, then G ₁? G ₂ is (2m+4??)-factor-critical, where ?=0 if m is even, otherwise ?=1;

iii. if m+2 ? |V(G ₁)|? 2m+2, or n+2? |V(G ₂)|? 2n+2, then G ₁? G ₂ is mn-factor-critical;

iv. if |V(G ₁)|? 2m+3 and |V(G ₂)|? 2n+3, then G ₁? G ₂ is (mn?min{[3m/2]₂, [3n/2]₂})-factor-critical.

     

Strongly (J,J′)‐lossless rational matrices and ℋ∞ problem

We strengthen the existing definition of (J,J′)‐lossless rational matrices (RMs) and find an algebraic characterization of the newly defined class of strongly (J,J′)‐lossless RMs. The algebraic characterization is given for possibly improper RMs. A connection is presented to a rational ? _∞ problem, known as the Leech problem, which is elaborated on with necessary and sufficient conditions, given in terms of the strongly (J,J′)‐lossless property, as an alternative of the Leech conditions, which can be expressed with positivity of a kernel. An algorithm for solving the Leech problem is given and illustrated by examples.     

Iterative solution of a class of linear equations with application to reconstruction of three-dimensional object arrays†

An iterative algorithm baaed on probabilistic estimation is described for obtaining the minimum-norm solution of a very large, consistent, linear system of equations AX = g where A is an (m × n) matrix with non-negative elements, x and g are respectively (n × 1) and (m × 1) vectors with positive components.

This algorithm will find application in the reconstruction of three-dimensional object arrays from projections and in several other areas.     

Constructive algorithm for system immersion into non-linear observer form

There exists a class of non-linear systems which cannot be transformed into a non-linear observer form (an observable linear system up to output injection) via diffeomorphism, but can be immersed into a higher dimensional non-linear observer form. This class of systems can be characterized by a differential equation called characteristic equation. If the system is an n dimensional system and it is immersible into n?+?m dimensional observer form, the characteristic equation involves n?+?m?+?1 unknowns where n?+?m unknowns are for the state immersion and one for the output transformation. In general, one should solve these unknowns simultaneously which makes the characterization difficult. After investigating the algebraic structure of the characteristic equation, we present an algorithm to check the immersibility under a constant rank assumption. Using the algorithm, one can check the immersibility iteratively since only one unknown is involved at each step of the algorithm.     

Algorithms of constructing a stabilizing solution of the algebraic Riccati equation based on its linear reduction in the problems of analytical construction of controllers

In the problem of the stabilizing solution of the algebraic Riccati equation, the resolvent Θ(s) = (s I _2n ? H)^?1 of the Hamilton 2n × 2n-matrix H of the algebraic Riccati equation allows us to reduce the problem to a linear matrix equation. In [1], the constructions necessary for this and the theorem of existence and representation of the stabilized solutions to an algebraic Riccati equation was proposed. In this paper, the methods of constructing the resolvent and the linear reduction matrix defined by it necessary for the application of the theorem, and in addition, the algorithms of constructing stabilizing solution of the algebraic Riccati equation are proposed.     

Least-squares problem for the quaternion matrix equation AXB+CYD=E over different constrained matrices

For any A=A ₁+A ₂ j∈Q ^n×n and η∈<texlscub>i, j, k</texlscub>, denote A ^{η H} =?η A ^H η. If A ^{η H} =A, A is called an $\eta$-Hermitian matrix. If A ^{η H} =?A, A is called an η-anti-Hermitian matrix. Denote η-Hermitian matrices and η-anti-Hermitian matrices by η HQ ^n×n and η AQ ^n×n , respectively.

By using the complex representation of quaternion matrices, the Moore–Penrose generalized inverse and the Kronecker product of matrices, we derive the expressions of the least-squares solution with the least norm for the quaternion matrix equation AXB+CYD=E over X∈η HQ ^n×n and Y∈η AQ ^n×n .