On the Euclidean TSP with a permuted Van der Veen matrix

We discuss the problem of recognizing permuted Van der Veen (VdV) matrices. It is well known that the TSP with a VdV matrix as distance matrix is pyramidally solvable. In this note we solve the problem of recognizing permuted strong VdV matrices. This yields an O(n⁴) time algorithm for the TSP with a permuted Euclidean VdV matrix. The problem, however, of recognizing permuted VdV matrices in general remains open.     

On the recognition of permuted Supnick and incomplete Monge matrices

Incomplete Monge matrices are a generalization of standard Monge matrices: the values of some entries are not specified and the Monge property only must hold for all specified entries. We derive several combinatorial properties of incomplete Monge matrices and prove that the problem of recognizingpermuted incomplete Monge matrices is NP-complete. For the special case of permutedSupnick matrices, we derive a fast recognition algorithm and thereby identify a special case of then-vertex travelling salesman problem which can be solved inO(n ²logn) time.     

Solving the generalized eigenvalue problem on a synchronous linear processor array

We present a parallel method to solve the generalized eigenvalue problem on a linear array of processors, each connected to their nearest neighbors and operating synchronously. We also include a wrap-around connection from end to end. Our method is based on the well-known QZ algorithm of Moler and Stewart, which simultaneously reduces two n × n matrices to upper triangular form by orthogonal or unitary transformations. We show how this algorithm may be partitioned and distributed of n + 1 processors, achieving a speed-up over the serial algorithm of O(n). We use the concept of windows to describe the action of each processor at each step. We show how to incorporate singles shifts, and how to apply orthogonal plane rotations on either side of a matrix without the need to transpose the matrix itself.     

Approximation algorithms for the bandwidth minimization problem for a large class of trees

We present approximation algorithms for the bandwidth minimization problem (BMP) for a large class of trees. The BMP is NP-hard, even for trees of maximum node degree 3. The problem finds applications in many areas, including VLSI layout, multiprocessor scheduling, and matrix processing, and has been studied for both graphs and matrices. We study the problem on trees having the following property: given any tree nodev, the depth difference of any two nonempty subtrees rooted atv is bounded by a constantk. We call such treesh(k)trees orgeneralized height-balanced (GHB)trees. The above definition extends the class of balanced trees to trees with depthd=Θ(\N\). For any tree in the above defined class, anO (logd) times optimal algorithm is presented. Furthermore, we extend the application of the algorithm to trees that simulate theh(k) property, which we callh(k)-like trees, and also provide intuitive ideas for an approximation algorithm for general trees.     

Time-slot assignment for TDMA-systems

In satellite communication as in other technical systems using the TDMA-technique (time division multiple access) the problem arises to decompose a given (n×n)-matrix in a weighted sum of permutation matrices such that the sum of the weights becomes minimal. We show at first that an optimal solution of this problem can be obtained inO(n ⁴)-time using at mostO(n ²) different permutation matrices. Thereafter we discuss shortly the decomposition inO(n) different matrices which turns out to be NP-hard. Moreover it is shown that an optimal decomposition using a class of 2n permutation matrices which are fixed in advance can be obtained by solving a classical assignment problem. This latter problem can be generalized by taking arbitrary Boolean matrices. The corresponding decomposition problem can be transformed to a special max flow min cost network flow problem, and is thus soluble by a genuinely polynomial algorithm.     

Pruning by dominance in best-first search for the job shop Scheduling problem with total flow time

Best-First search is a problem solving paradigm that allows to design exact or admissible algorithms. In this paper, we confront the Job Shop Scheduling problem with total flow time minimization by means of the A ^* algorithm. We devised a heuristic from a problem relaxation that relies on computing Jackson’s preemptive schedules. In order to reduce the effective search space, we formalized a method for pruning nodes based on dominance relations and established a rule to apply this method efficiently during the search. By means of experimental study, we show that the proposed method is more efficient than a genetic algorithm in solving instances with 10 jobs and 5 machines and that pruning by dominance allows A ^* to reach optimal schedules, while these instances are not solved by A ^* otherwise. These experiments have also made it clear that the Job Shop Scheduling problem with total flow time minimization is harder to solve than the same problem with makespan minimization.     

Calculation of the permanent of a sparse positive matrix

The exact calculation of permanents of n×n matrices is a non-polynomial computational problem as a function of n. An efficient deterministic algorithm is presented that allows for the approximate calculation of permanents obtained from sparse positive matrices within controllable precision bounds. The upper and lower bounds can be made arbitrarily close to each other and the algorithm outperforms existing ones for sufficiently large matrices.     

Extreme eigenvalues of large sparse matrices by Rayleigh quotient and modified conjugate gradients

The extreme eigenvalues of a symmetric positive-definite matrix A may be obtained as the solution to an extremum problem, namely through the minimization or the maximization of the Rayleigh quotient by the conjugate gradients. While this procedure works well for the upper bound λ₁, its rate of convergence proves too slow for the lower bound λ_N. For large sparse matrices the iteration can be extraordinarily accelerated with the aid of a preconditioning matrix derived from the incomplete Cholesky factorization of A. The new scheme has been applied to determine the smallest eigenvalue of finite element matrices of size N, with N between 150 and 2220 taken from the engineering practice. The results show that a good estimate of λ_N is achieved after very few iterations and that the Rayleigh quotient/modified conjugate gradient technique is more than one order of magnitude faster than the reverse power/conjugate gradient algorithm recently developed by the authors for the same problem.     

Minimization of earliness, tardiness and due date penalties on uniform parallel machines with identical jobs

We consider a problem of scheduling n identical nonpreemptive jobs with a common due date on m uniform parallel machines. The objective is to determine an optimal value of the due date and an optimal allocation of jobs onto machines so as to minimize a total cost function, which is the function of earliness, tardiness and due date values. For the problem under study, we establish a set of properties of an optimal solution and suggest a two-phase algorithm to tackle the problem. First, we limit the number of due dates one needs to consider in pursuit of optimality. Next, we provide a polynomial-time algorithm to build an optimal schedule for a fixed due date. The key result is an O(m² log m) algorithm that solves the main problem to optimality.Scope and purpose: To extend the existing research on cost minimization with earliness, tardiness and due date penalties to the case of uniform parallel machines.     

Image Restoration with Discrete Constrained Total Variation Part I: Fast and Exact Optimization

This paper deals with the total variation minimization problem in image restoration for convex data fidelity functionals. We propose a new and fast algorithm which computes an exact solution in the discrete framework. Our method relies on the decomposition of an image into its level sets. It maps the original problems into independent binary Markov Random Field optimization problems at each level. Exact solutions of these binary problems are found thanks to minimum cost cut techniques in graphs. These binary solutions are proved to be monotone increasing with levels and yield thus an exact solution of the discrete original problem. Furthermore we show that minimization of total variation under L ¹ data fidelity term yields a self-dual contrast invariant filter. Finally we present some results.     

A new algorithm for resolution of the quadratic programming problem with fuzzy relation inequality constraints

The minimization problem of a quadratic objective function with the max-product fuzzy relation inequality constraints is studied in this paper. In this problem, its objective function is not necessarily convex. Hence, its Hessian matrix is not necessarily positive semi-definite. Therefore, we cannot apply the modified simplex method to solve this problem, in a general case. In this paper, we firstly study the structure of its feasible domain. We then use some properties of n × n real symmetric indefinite matrices, Cholesky’s decomposition, and the least square technique, and convert the problem to a separable programming problem. Furthermore, a relation in terms of a closed form is presented to solve it. Finally, an algorithm is proposed to solve the original problem. An application example in the economic area is given to illustrate the problem. Of course, there are other application examples in the area of digital data service and reliability engineering.     

A parallel algorithm for functions of triangular matrices

We present a new parallel algorithm for computing arbitrary functions of triangular matrices. The presented algorithm is the first one to date requiring polylogarithmic time, and computes an arbitrary function of ann×n triangular matrix in O(log³ n) time using O(n ⁶) processors. The algorithm requires the eigenvalues of the input matrix be distinct, and makes use of the commutativity relationship between the input and output matrices.     

L 1 shortest paths among polygonal obstacles in the plane

We present an algorithm for computingL ₁ shortest paths among polygonal obstacles in the plane. Our algorithm employs the “continuous Dijkstra” technique of propagating a “wavefront” and runs in timeO(E logn) and spaceO(E), wheren is the number of vertices of the obstacles andE is the number of “events.” By using bounds on the density of certain sparse binary matrices, we show thatE =O(n logn), implying that our algorithm is nearly optimal. We conjecture thatE =O(n), which would imply our algorithm to be optimal. Previous bounds for our problem were quadratic in time and space. Our algorithm generalizes to the case of fixed orientation metrics, yielding anO(n?^?1/2 log² n) time andO(n?^?1/2) space approximation algorithm for finding Euclidean shortest paths among obstacles. The algorithm further generalizes to the case of many sources, allowing us to compute anL ₁ Voronoi diagram for source points that lie among a collection of polygonal obstacles.     

Approximation Algorithms for Minimizing Edge Crossings in Radial Drawings

We study a crossing minimization problem of drawing a bipartite graph with a radial drawing of two orbits. Radial drawings are one of well-known drawing conventions in social network analysis and visualization, in particular, displaying centrality indices of actors (Wasserman and Faust, Social Network Analysis: Methods and Applications. Cambridge University Press, Cambridge, 1994). The main problem in this paper is called the one-sided radial crossing minimization, if the positions of vertices in the outer orbit are fixed. The problem is known to be NP-hard (Bachmaier, IEEE Trans. Vis. Comput. Graph. 13, 583–594, 2007), and a number of heuristics are available (Bachmaier, IEEE Trans. Vis. Comput. Graph. 13, 583–594, 2007). However, there is no approximation algorithm for the crossing minimization problem in radial drawings. We present the first polynomial time constant-factor approximation algorithm for the one-sided radial crossing minimization problem.     

Faster Combinatorial Algorithms for Determinant and Pfaffian

Computation of a determinant is a very classical problem. The related concept is a Pfaffian of a matrix defined for skew-symmetric matrices. The classical algorithm for computing the determinant is Gaussian elimination. It needs O(n ³) additions, subtractions, multiplications and divisions. The algorithms of Mahajan and Vinay compute determinant and Pfaffian in a completely non-classical and combinatorial way, by reducing these problems to summation of paths in some acyclic graphs. The attractive feature of these algorithms is that they are division-free. We present a novel algebraic view of these algorithms: a relation to a pseudo-polynomial dynamic-programming algorithm for the knapsack problem. The main phase of Mahajan-Vinay algorithm can be interpreted as a computation of an algebraic version of the knapsack problem, which is an alternative to the graph-theoretic approach used in the original algorithm. Our main results show how to implement Mahajan-Vinay algorithms without divisions, in time $\tilde{O}(n^{3.03})$ using the fast matrix multiplication algorithm.     

Conjugate gradient type methods for semilinear elliptic problems with symmetry

We study block conjugate gradient methods in the context of continuation methods for bifurcation problems. By exploiting symmetry in certain semilinear elliptic differential equations, we can decompose the problems into small ones and reduce computational cost. On the other hand, the associated centered difference discretization matrices on the subdomains are nonsymmetric. We symmetrize them by using simple similarity transformations and discuss some basic properties concerning the discretization matrices. These properties allow the discrete pure mode solution paths branching from a multiple bifurcation point [0, λ^m,n] of the centered difference analogue of the original problem to be represented by the solution path branching from the first simple bifurcation point (0, μ^1,1) of the counterpart of the reduced problem. Thus, the structure of a multiple bifurcation is preserved in discretization, while its treatment is reduced to those for simple bifurcation of problems on subdomains. In particular, we can adapt the continuation-Lanczos algorithm proposed in [1] to trace simple solution paths. Sample numerical results are reported.     

Unitary invariant discord as a measures of bipartite quantum correlations in an N-qubit quantum system

We introduce a measure of quantum correlations in the N-qubit quantum system which is invariant with respect to the SU(2 ^N ) group of transformations of this system. This measure is a modification of the quantum discord introduced earlier and is referred to as the unitary or SU(2 ^N )-invariant discord. Since the evolution of a quantum system is equivalent to the proper unitary transformation, the introduced measure is an integral of motion and is completely defined by eigenvalues of the density matrix. As far as the calculation of the unitary invariant discord is rather complicated computational problem, we propose its modification which may be found in a simpler way. The case N?=?2 is considered in details. In particular, it is shown that the modified SU(4)-invariant discord reaches the maximum value for a pure state. A geometric measure of the unitary invariant discord of an N-qubit state is introduced and a simple formula for this measure is derived, which allows one to consider this measure as a witness of quantum correlations. The relation of the unitary invariant discord with the quantum state transfer along the spin chain is considered. We also compare the modified SU(4)-invariant discord with the geometric measure of SU(4)-invariant discord of the two-qubit systems in the thermal equilibrium states governed by the different Hamiltonians.     

Computations with quasiseparable polynomials and matrices

In this paper, we survey several recent results that highlight an interplay between a relatively new class of quasiseparable matrices and univariate polynomials. Quasiseparable matrices generalize two classical matrix classes, Jacobi (tridiagonal) matrices and unitary Hessenberg matrices that are known to correspond to real orthogonal polynomials and Szegö polynomials, respectively. The latter two polynomial families arise in a wide variety of applications, and their short recurrence relations are the basis for a number of efficient algorithms. For historical reasons, algorithm development is more advanced for real orthogonal polynomials. Recent variations of these algorithms tend to be valid only for the Szegö polynomials; they are analogues and not generalizations of the original algorithms.     

On Minimum Witnesses for Boolean Matrix Multiplication

Minimum witnesses for Boolean matrix multiplication play an important role in several graph algorithms. For two Boolean matrices A and B of order n, with one of the matrices having at most m nonzero entries, the fastest known algorithms for computing the minimum witnesses of their product run in either O(n ^2.575) time or in O(n ²+mnlog(n ²/m)/log² n) time. We present a new algorithm for this problem. Our algorithm runs either in time $$\tilde{O}\bigl(n^{\frac{3}{4-\omega}}m^{1-\frac{1}{4-\omega }}\bigr) $$ where ω<2.376 is the matrix multiplication exponent, or, if fast rectangular matrix multiplication is used, in time $$O\bigl(n^{1.939}m^{0.318}\bigr). $$ In particular, if ω?1<α<2 where m=n ^α , the new algorithm is faster than both of the aforementioned algorithms.