A new bidirectional search algorithm with shortened postprocessing

For finding a shortest path in a network bidirectional A^∗ is a widely known algorithm. This algorithm distinguishes between the main phase and the postprocessing phase. The version of bidirectional A^∗ that is considered the most appropriate in literature hitherto, uses a so-called balanced heuristic estimate. This type of heuristic is chosen, as it accounts for a short postprocessing phase. In this paper, we do not restrict ourselves any longer to balanced heuristics. First, we introduce an algorithm containing a new method for the postprocessing phase, reducing this phase considerably for non-balanced heuristics. For a balanced heuristic the new algorithm is nearly equivalent to the existing versions of bidirectional A^∗. An obvious choice for a non-balanced heuristic turns out to be superior in terms of storage space and computation time. Second, we show that the main phase on its own, when using this non-balanced heuristic estimate, is a useful algorithm, which provides us quickly with a feasible approximation.     

Controlling arrivals for a queueing system with an unreliable server: Newton-Quasi method

This paper deals with the control policy of a removable and unreliable server for an M/M/1/K queueing system, where the removable server operates an F-policy. The so-called F-policy means that when the number of customers in the system reaches its capacity K (i.e. the system becomes full), the system will not accept any incoming customers until the queue length decreases to a certain threshold value F. At that time, the server initiates an exponential startup time with parameter γ and starts allowing customers entering the system. It is assumed that the server breaks down according to a Poisson process and the repair time has an exponential distribution. A matrix analytical method is applied to derive the steady-state probabilities through which various system performance measures can be obtained. A cost model is constructed to determine the optimal values, say (F^∗, μ^∗, γ^∗), that yield the minimum cost. Finally, we use the two methods, namely, the direct search method and the Newton-Quasi method to find the global minimum (F^∗, μ^∗, γ^∗). Numerical results are also provided under optimal operating conditions.     

A geometric process maintenance model with preventive repair

In this paper, a geometric process maintenance model with preventive repair is studied. A maintenance policy (T, N) is applied by which the system will be repaired whenever it fails or its operating time reaches T whichever occurs first, and the system will be replaced by a new and identical one following the Nth failure. The long-run average cost per unit time is determined. An optimal policy (T^∗, N^∗) could be determined numerically or analytically for minimizing the average cost. A new class of lifetime distribution which takes into account the effect of preventive repair is studied that is applied to determine the optimal policy (T^∗, N^∗).     

Existence of spectral well-behaved ∗-representations

There are several cases, where an m^∗-seminorm p is defined on a ∗-subalgebra of a given ∗-algebra A. This may lead to the construction of an unbounded ∗-representation of A. Such m^∗-seminorms are called unbounded. Given an unbounded m^∗-seminorm p of a ∗-algebra A, the concept of a p-spectral ∗-representation of A is introduced and studied in connection to well-behaved ∗-representations. More precisely, the existence of (p-) spectral well-behaved ∗-representations is investigated on ∗-algebras and locally convex ∗-algebras in terms of certain properties of Pták function, closely related to hermiticity and C^∗-spectrality of the ∗-subalgebras on which this function is defined. Various examples in diverse classes of locally convex algebras illuminate the elaborated results.     

Simulated annealing for the unconstrained quadratic pseudo-Boolean function

In this paper, we develop a simulated annealing (SA) based heuristic for the unconstrained quadratic pseudo-Boolean function. An algorithm that solves the problem in O(n²) at each temperature of the cooling schedule is given. The performance of SA based heuristic is compared with existing bounding algorithms for this problem. Computational results and comparisons on several hundred test problems demonstrate the efficiency of our heuristic in terms of solution quality and computational time. A new set of hard test problems with their best solution is provided to facilitate future comparison.     

Impulsive epidemic model with differential susceptibility and stage structure

A stage-structured epidemic model with two differential susceptible of susceptibility and pulse vaccination is proposed. We introduce two thresholds R^∗ and R_∗, and further prove that a disease cannot invade the disease-free state if R^∗ is less than unit and can invade if R^∗ is larger than unit. Two numerical simulations are also given to illustrate our main results.     

A modified variable neighborhood search for the discrete ordered median problem

This paper presents a modified Variable Neighborhood Search (VNS) heuristic algorithm for solving the Discrete Ordered Median Problem (DOMP). This heuristic is based on new neighborhoods’ structures that allow an efficient encoding of the solutions of the DOMP avoiding sorting in the evaluation of the objective function at each considered solution. The algorithm is based on a data structure, computed in preprocessing, that organizes the minimal necessary information to update and evaluate solutions in linear time without sorting. In order to investigate the performance, the new algorithm is compared with other heuristic algorithms previously available in the literature for solving DOMP. We report on some computational experiments based on the well-known N-median instances of the ORLIB with up to 900 nodes. The obtained results are comparable or superior to existing algorithms in the literature, both in running times and number of best solutions found.     

Lie algebras generated by bounded linear operators on Hilbert spaces

It is proved that the operator Lie algebra ε(T,T^∗) generated by a bounded linear operator T on Hilbert space H is finite-dimensional if and only if T=N+Q, N is a normal operator, [N,Q]=0, and dimA(Q,Q^∗)<+∞, where ε(T,T^∗) denotes the smallest Lie algebra containing T,T^∗, and A(Q,Q^∗) denotes the associative subalgebra of B(H) generated by Q,Q^∗. Moreover, we also give a sufficient and necessary condition for operators to generate finite-dimensional semi-simple Lie algebras. Finally, we prove that if ε(T,T^∗) is an ad-compact E-solvable Lie algebra, then T is a normal operator.     

Minimal ranks of some quaternion matrix expressions with applications

Suppose that p(X, Y) = A − BX − X^(∗)B^(∗) − CYC^(∗) and q(X, Y) = A − BX + X^(∗)B^(∗) − CYC^(∗) are quaternion matrix expressions, where A is persymmetric or perskew-symmetric. We in this paper derive the minimal rank formula of p(X, Y) with respect to pair of matrices X and Y = Y^(∗), and the minimal rank formula of q(X, Y) with respect to pair of matrices X and Y = −Y^(∗). As applications, we establish some necessary and sufficient conditions for the existence of the general (persymmetric or perskew-symmetric) solutions to some well-known linear quaternion matrix equations. The expressions are also given for the corresponding general solutions of the matrix equations when the solvability conditions are satisfied. At the same time, some useful consequences are also developed.     

On disjoint range matrices

For a square complex matrix F and for F^∗ being its conjugate transpose, the class of matrices satisfying R(F)∩R(F^∗)={0}, where R(.) denotes range (column space) of a matrix argument, is investigated. Besides identifying a number of its properties, several functions of F, such as F+F^∗, (F:F^∗), FF^∗+F^∗F, and F-F^∗, are considered. Particular attention is paid to the Moore-Penrose inverses of those functions and projectors attributed to them. It is shown that some results scattered in the literature, whose complexity practically prevents them from being used to deal with real problems, can be replaced with much simpler expressions when the ranges of F and F^∗ are disjoint. Furthermore, as a by-product of the derived formulae, one obtains a variety of relevant facts concerning, for instance, rank and range.     

A note about proving non-Γ under a finite non-microstates free Fisher information assumption

We prove that if X₁,…,Xn (n>1) are self-adjoints in a W^∗-probability space with finite non-microstates free Fisher information, then the von Neumann algebra W^∗(X₁,…,Xn) they generate doesn't have property Γ (especially is not amenable). This is an analog of a well-known result of Voiculescu for microstates free entropy. We also prove factoriality under finite non-microstates entropy.     

On (0, 1)-matrices with prescribed row and column sum vectors

Given partitions R and S with the same weight, the Robinson-Schensted-Knuth correspondence establishes a bijection between the class A(R,S) of (0, 1)-matrices with row sum R and column sum S and pairs of Young tableaux of conjugate shapes λ and λ^∗, with S?λ?R^∗. An algorithm for constructing a matrix in A(R,S) whose insertion tableau has a prescribed shape λ, with S?λ?R^∗, is provided. We generalize some recent constructions due to R. Brualdi for the extremal cases λ=S and λ=R^∗.     

Weighted heuristic search in networks

The evaluation function used in heuristic search algorithms commonly has the form , where n is any node in the network, is the cost of the best path currently known from the start node to n, and is the heuristic estimate associated with node n. A more general form of the evaluation function can be obtained by incorporating a weighting parameter α:

Full-size image

, where 0≤ α ≤1. Such an evaluation function has been used in some recent experimental investigations of the 8-puzzle problem. In this paper a theoretical framework is developed for the analysis of the worst-case behavior of weighted heuristic search algorithms. A new algorithm is proposed whose worst-case performance characteristics are greatly superior to those of earlier algorithms in terms of the following two measures: how good is the solution, and how many nodes are expanded. Bounds are also obtained on some useful network parameters for both general and special types of heuristic estimate functions.     

Piecewise testable languages via combinatorics on words

A regular language L over an alphabet A is called piecewise testable if it is a finite Boolean combination of languages of the form A^∗a₁A^∗a₂A^∗…A^∗a_?A^∗, where a₁,…,a_?∈A, ?≥0. An effective characterization of piecewise testable languages was given in 1972 by Simon who proved that a language L is piecewise testable if and only if its syntactic monoid is J-trivial. Nowadays, there exist several proofs of this result based on various methods from algebraic theory of regular languages. Our contribution adds a new purely combinatorial proof.     

On relations between weak approximation properties and their inheritances to subspaces

It is shown that for the separable dual X^∗ of a Banach space X, if X^∗ has the weak approximation property, then X^∗ has the metric weak approximation property. We introduce the properties W^∗D and MW^∗D for Banach spaces. Suppose that M is a closed subspace of a Banach space X such that M^⊥ is complemented in the dual space X^∗, where for all m∈M}. Then it is shown that if a Banach space X has the weak approximation property and W^∗D (respectively, metric weak approximation property and MW^∗D), then M has the weak approximation property (respectively, bounded weak approximation property).     

James orthogonality and orthogonal decompositions of Banach spaces

We establish decompositions of a uniformly convex and uniformly smooth Banach space B and dual space B^∗ in the form B=M?J^∗M^⊥ and B^∗=M^⊥?JM, where M is an arbitrary subspace in B, M^⊥ is its annihilator (subspace) in B^∗, J:B→B^∗ and J^∗:B^∗→B are normalized duality mappings. The sign ? denotes the James orthogonal summation (in fact, it is the direct sums of the corresponding subspaces and manifolds). In a Hilbert space H, these representations coincide with the classical decomposition in a shape of direct sum of the subspace M and its orthogonal complement M^⊥: H=M⊕M^⊥.     

An iterated local search algorithm for the vehicle routing problem with backhauls

The Vehicle Routing Problem with Backhauls (VRPB) is an extension of the VRP that deals with two types of customers: the consumers (linehaul) that request goods from the depot and the suppliers (backhaul) that send goods to the depot. In this paper, we propose a simple yet effective iterated local search algorithm for the VRPB. Its main component is an oscillating local search heuristic that has two main features. First, it explores a broad neighborhood structure at each iteration. This is efficiently done using a data structure that stores information about the set of neighboring solutions. Second, the heuristic performs constant transitions between feasible and infeasible portions of the solution space. These transitions are regulated by a dynamic adjustment of the penalty applied to infeasible solutions. An extensive statistical analysis was carried out in order to identify the most important components of the algorithm and to properly tune the values of their parameters. The results of the computational experiments carried out show that this algorithm is very competitive in comparison to the best metaheuristic algorithms for the VRPB. Additionally, new best solutions have been found for two instances in one of the benchmark sets. These results show that the performance of existing metaheuristic algorithms can be considerably improved by carrying out a thorough statistical analysis of their components. In particular, it shows that by expanding the exploration area and improving the efficiency of the local search heuristic, it is possible to develop simpler and faster metaheuristic algorithms without compromising the quality of the solutions obtained.     

Weak exactness for dual operator spaces

We introduce a new tensor product and study the weak^∗ condition C^′, which is also called weak^∗ exactness, for dual operator spaces. Our definition of weak^∗ condition C^′ is equivalent to Kirchberg's notion of weak exactness in the case of von Neumann algebras. We also study the connection of weak^∗ exact W^∗-TROs with their linking von Neumann algebras and study the structure of exact (respectively, nuclear) W^∗-TROs.     

Dirichlet-like space and capacity in complex analysis in several variables

For a Kähler manifold X, we study a space of test functions W^∗ which is a complex version of W1,2. We prove for W^∗ the classical results of the theory of Dirichlet spaces: the functions in W^∗ are defined up to a pluripolar set and the functional capacity associated to W^∗ tests the pluripolar sets. This functional capacity is a Choquet capacity. The space W^∗ is not reflexive and the smooth functions are not dense in it for the strong topology. So the classical tools of potential theory do not apply here. We use instead pluripotential theory and Dirichlet spaces associated to a current.     

Nonstandard étale cohomology

A lot of good properties of étale cohomology only hold for torsion coefficients. We use ultraproducts respectively enlargement construction to define a cohomology theory that inherits the important properties of étale cohomology while allowing greater flexibility with the coefficients. In particular, choosing coefficients ^∗Z/P^∗Z (for P an infinite prime and ^∗Z the enlargement of Z) gives a Weil cohomology, and choosing ^∗Z/l^h∗Z (for l a finite prime and h an infinite number) allows comparison with ordinary l-adic cohomology. More generally, for every N∈^∗Z, we get a category of ^∗Z/N^∗Z-constructible sheaves with good properties.