On parallel Branch and Bound frameworks for Global Optimization

Branch and Bound (B&B) algorithms are known to exhibit an irregularity of the search tree. Therefore, developing a parallel approach for this kind of algorithms is a challenge. The efficiency of a B&B algorithm depends on the chosen Branching, Bounding, Selection, Rejection, and Termination rules. The question we investigate is how the chosen platform consisting of programming language, used libraries, or skeletons influences programming effort and algorithm performance. Selection rule and data management structures are usually hidden to programmers for frameworks with a high level of abstraction, as well as the load balancing strategy, when the algorithm is run in parallel. We investigate the question by implementing a multidimensional Global Optimization B&B algorithm with the help of three frameworks with a different level of abstraction (from more to less): Bobpp, Threading Building Blocks (TBB), and a customized Pthread implementation. The following has been found. The Bobpp implementation is easy to code, but exhibits the poorest scalability. On the contrast, the TBB and Pthread implementations scale almost linearly on the used platform. The TBB approach shows a slightly better productivity.     

On the number of derangements and derangements of prime power order of the affine general linear groups

A derangement is a permutation that has no fixed points. In this paper, we are interested in the proportion of derangements of the finite affine general linear groups. We prove a remarkably simple and explicit formula for this proportion. We also give a formula for the proportion of derangements of prime power order. Both formulae rely on a result of independent interest on partitions: we determine the generating function for the partitions with m parts and with the kth largest part not k, for every \(k\in \mathbb {N}\).     

Schur-positive sets of permutations via products and grid classes

Characterizing sets of permutations whose associated quasisymmetric function is symmetric and Schur-positive is a long-standing problem in algebraic combinatorics. In this paper, we present a general method to construct Schur-positive sets and multisets, based on geometric grid classes and the product operation. Our approach produces many new instances of Schur-positive sets and provides a broad framework that explains the existence of known such sets that until now were sporadic cases.     

Perfect contrast XOR-based visual cryptography schemes via linear algebra

XOR-based visual cryptography scheme (XVCS) was proposed to solve the poor visual quality problem without darkening the background in the reconstructed secret image. However, investigations on XVCS are not sufficient. In this paper, we focus on the traditional model of VCS for general access structures and exploit some extended capabilities for XVCS. Our main contributions are: (1) we put forward constructions of perfect contrast XVCS using the linear algebraic technique without any assumptions such as participants may carry multiple shares or prior information about the shares are to be submitted during the secret reconstruction phase; (2) for some restricted access structures, we achieve perfect contrast and perfect pixel expansion, namely both 1, which is impossible for any OR-based visual cryptography scheme (OVCS); (3) for general access structures, we achieve perfect contrast with smaller pixel expansion compared with many of the results in the literature; (4) Theoretical analysis on the proposed constructions are provided, as well as extensive experimental results and comparisons for demonstrating the effectiveness and advantages of our constructions.     

On Pimsner–Popa bases

In this paper, we examine bases for finite index inclusion of II₁ factors and connected inclusion of finite dimensional C ^?-algebras. These bases behave nicely with respect to basic construction towers. As applications we have studied automorphisms of the hyperfinite II₁ factor R which are ‘compatible with respect to the Jones’ tower of finite dimensional C ^?-algebras’. As a further application, in both cases we obtain a characterization, in terms of bases, of basic constructions. Finally we use these bases to describe the phenomenon of multistep basic constructions (in both the cases).     

Qualitative behaviour of incompressible two-phase flows with phase transitions: The isothermal case

A thermodynamically consistent model for incompressible two-phase flows with phase transitions is considered mathematically. The model is based on first principles, i.e., balance of mass, momentum and energy. In the isothermal case, this problem is analysed to obtain local well-posedness, stability of non-degenerate equilibria, and global existence and convergence to equilibria of solutions which do not develop singularities.     

Matrix-analytic solution of infinite,finite and level-dependent second-order fluid models

This paper presents a matrix-analytic solution for second-order Markov fluid models (also known as Markov-modulated Brownian motion) with level-dependent behavior. A set of thresholds is given that divide the fluid buffer into homogeneous regimes. The generator matrix of the background Markov chain, the fluid rates (drifts) and the variances can be regime dependent. The model allows the mixing of second-order states (with positive variance) and first-order states (with zero variance) and states with zero drift. The behavior at the upper and lower boundary can be reflecting, absorbing, or a combination of them. In every regime, the solution is expressed as a matrix-exponential combination, whose matrix parameters are given by the minimal nonnegative solution of matrix quadratic equations that can be obtained by any of the well-known solution methods available for quasi birth death processes. The probability masses and the initial vectors of the matrix-exponential terms are the solutions of a set of linear equations. However, to have the necessary number of equations, new relations are required for the level boundary behavior, relations that were not needed in first-order level dependent and in homogeneous (non-level-dependent) second-order fluid models. The method presented can solve systems with hundreds of states and hundreds of thresholds without numerical issues.     

Correction to “Queue-proportional rate allocation with per-link information in multihop wireless networks”

There is a gap in the proofs of both Propositions 3 and 4 in the correspondence “Queue-Proportional Rate Allocation with Per-Link Information in Multihop Wireless Networks,” previously published in the Queueing Systems (see Li and Srikant 2016). We filled this gap in the proofs for the multihop networks (see Li and Srikant in Queueing Syst 84:203–210, 2016), where each route at most has two links. In this note, we completely fill the gap in the proofs in our original paper (see Li and Srikant in Queueing Syst 83:329–359, 2016).     

Fast implementation of the Tukey depth

Tukey depth function is one of the most famous multivariate tools serving robust purposes. It is also very well known for its computability problems in dimensions \(p \ge 3\). In this paper, we address this computing issue by presenting two combinatorial algorithms. The first is naive and calculates the Tukey depth of a single point with complexity \(O\left( n^{p-1}\log (n)\right) \), while the second further utilizes the quasiconcave of the Tukey depth function and hence is more efficient than the first. Both require very minimal memory and run much faster than the existing ones. All experiments indicate that they compute the exact Tukey depth.     

A non-negative matrix factorization model based on the zero-inflated Tweedie distribution

Non-negative matrix factorization (NMF) is a technique of multivariate analysis used to approximate a given matrix containing non-negative data using two non-negative factor matrices that has been applied to a number of fields. However, when a matrix containing non-negative data has many zeroes, NMF encounters an approximation difficulty. This zero-inflated situation occurs often when a data matrix is given as count data, and becomes more challenging with matrices of increasing size. To solve this problem, we propose a new NMF model for zero-inflated non-negative matrices. Our model is based on the zero-inflated Tweedie distribution. The Tweedie distribution is a generalization of the normal, the Poisson, and the gamma distributions, and differs from each of the other distributions in the degree of robustness of its estimated parameters. In this paper, we show through numerical examples that the proposed model is superior to the basic NMF model in terms of approximation of zero-inflated data. Furthermore, we show the differences between the estimated basis vectors found using the basic and the proposed NMF models for \(\beta \) divergence by applying it to real purchasing data.