A hybrid shifting bottleneck procedure algorithm for the parallel-machine job-shop scheduling problem

In practice, parallel-machine job-shop scheduling (PMJSS) is very useful in the development of standard modelling approaches and generic solution techniques for many real-world scheduling problems. In this paper, based on the analysis of structural properties in an extended disjunctive graph model, a hybrid shifting bottleneck procedure (HSBP) algorithm combined with Tabu Search (TS) metaheuristic algorithm is developed to deal with the PMJSS problem. The original-version shifting bottleneck procedure (SBP) algorithm for the job-shop scheduling (JSS) has been significantly improved to solve the PMJSS problem with four novelties: (i) a topological-sequence algorithm is proposed to decompose the PMJSS problem in a set of single-machine scheduling (SMS) and/or parallel-machine scheduling subproblems; (ii) a modified Carlier algorithm based on the proposed lemmas and the proofs is developed to solve the SMS subproblem; (iii) the Jackson rule is extended to solve the PMS subproblem; (iv) a TS metaheuristic algorithm is embedded under the framework of SBP to optimise the JSS and PMJSS cases. The computational experiments show that the proposed HSBP is very efficient in solving the JSS and PMJSS problems.     

Asymptotically optimal approach to the approximate solution of several problems of covering a graph by nonadjacent cycles

We consider the m-Cycle Cover Problem of covering a complete undirected graph by m vertex-nonadjacent cycles of extremal total edge weight. The so-called TSP approach to the construction of an approximation algorithm for this problem with the use of a solution of the traveling salesman problem (TSP) is presented. Modifications of the algorithm for the Euclidean Max m-Cycle Cover Problem with deterministic instances (edge weights) in a multidimensional Euclidean space and the Random Min m-Cycle Cover Problem with random instances UNI(0,1) are analyzed. It is shown that both algorithms have time complexity O(n ³) and are asymptotically optimal for the number of covering cycles m = o(n) and \(m \leqslant \frac{{n^{1/3} }}{{\ln n}}\), respectively.     

Two Bilinear (3 × 3)-Matrix Multiplication Algorithms of Complexity 25

As is known, a bilinear algorithm for multiplying 3 × 3 matrices can be constructed by using ordered triples of 3 × 3 matrices A _ρ , B _ρ , C _ρ , \(\rho = \overline {1,r} ,\) where r is the complexity of the algorithm. Algorithms with various symmetries are being extensively studied. This paper presents two algorithms of complexity 25 possessing the following two properties (symmetries): (1) the matricesA₁,B₁, and C1 are identity, (2) if the algorithm involves a tripleA, B, C, then it also involves the triples B, C, A and C, A, B. For example, these properties are inherent in the well-known Strassen algorithm for multiplying 2 × 2 matrices. Many existing (3 × 3)-matrix multiplication algorithms have property (2). Methods for finding new algorithms are proposed. It is shown that the found algorithms are different and new.     

Fast separation for the three-index assignment problem

A critical step in a cutting plane algorithm is separation, i.e., establishing whether a given vector x violates an inequality belonging to a specific class. It is customary to express the time complexity of a separation algorithm in the number of variables n. Here, we argue that a separation algorithm may instead process the vector containing the positive components of x,  denoted as supp(x),  which offers a more compact representation, especially if x is sparse; we also propose to express the time complexity in terms of |supp(x)|. Although several well-known separation algorithms exploit the sparsity of x,  we revisit this idea in order to take sparsity explicitly into account in the time-complexity of separation and also design faster algorithms. We apply this approach to two classes of facet-defining inequalities for the three-index assignment problem, and obtain separation algorithms whose time complexity is linear in |supp(x)| instead of n. We indicate that this can be generalized to the axial k-index assignment problem and we show empirically how the separation algorithms exploiting sparsity improve on existing ones by running them on the largest instances reported in the literature.     

A Note on Average-Case Sorting

This note studies the average-case comparison-complexity of sorting n elements when there is a known distribution on inputs and the goal is to minimize the expected number of comparisons. We generalize Fredman’s algorithm which is a variant of insertion sort and provide a basically tight upper bound: If μ is a distribution on permutations on n elements, then one may sort inputs from μ with expected number of comparisons that is at most H(μ) + 2n, where H is the entropy function. The algorithm uses less comparisons for more probable inputs: For every permutation π, the algorithm sorts π by using at most \(\log _{2}(\frac {1}{\Pr _{\mu }(\pi )})+2n\) comparisons. A lower bound on the expected number of comparisons of H(μ) always holds, and a linear dependence on n is also required.     

A new heuristic approach for the P-median problem

The Euclidean p-median problem is concerned with the decision of the locations for public service centres. Existing methods for the planar Euclidean p-median problems are capable of efficiently solving problems of relatively small scale. This paper proposes two new heuristic algorithms aiming at problems of large scale. Firstly, to reflect the different degrees of proximity to optimality, a new kind of local optimum called level-m optimum is defined. For a level-m optimum of a p-median problem, where m<p, each of its subsets containing m of the p partitions is a global optimum of the corresponding m-median subproblem. Starting from a conventional local optimum, the first new algorithm efficiently improves it to a level-2 optimum by applying an existing exact algorithm for solving the 2-median problem. The second new algorithm further improves it to a level-3 optimum by applying a new exact algorithm for solving the 3-median problem. Comparison based on experimental results confirms that the proposed algorithms are superior to the existing heuristics, especially in terms of solution quality.     

Calculation of Bezout’s coefficients for the <Emphasis Type="Italic">k</Emphasis>-ary algorithm of finding GCD

Bezout’s equation is a representation of the greatest common divisor d of integers A and B as a linear combination Ax + By = d, where x and y are integers called Bezout’s coefficients. The task of finding Bezout’s coefficients has numerous applications in the number theory and cryptography, for example, for calculation of multiplicative inverse elements in modular arithmetic. Usually Bezout’s coefficients are caclulated using the extended version of the classical Euclidian algorithm.We elaborate a new algorithm for calculating Bezout’s coefficients based on the k-ary GCD algorithm.     

How to make a linear network code (strongly) secure

A linear network code is called k-secure if it is secure even if an adversary eavesdrops at most k edges. In this paper, we show an efficient deterministic construction algorithm of a linear transformation T that transforms an (insecure) linear network code to a k-secure one for any k, and extend this algorithm to strong k-security for any k . Our algorithms run in polynomial time if k is a constant, and these time complexities are explicitly presented. We also present a concrete size of \(|\mathsf{F}|\) for strong k-security, where \(\mathsf{F}\) is the underling finite field.     

Redundant <Emphasis Type="Italic">τ</Emphasis>-adic expansions I: non-adjacent digit sets and their applications to scalar multiplication

This paper investigates some properties of τ-adic expansions of scalars. Such expansions are widely used in the design of scalar multiplication algorithms on Koblitz curves, but at the same time they are much less understood than their binary counterparts. Solinas introduced the width-w τ-adic non-adjacent form for use with Koblitz curves. This is an expansion of integers \({z = \sum_{i=0}^\ell z_i \tau^i}\) , where τ is a quadratic integer depending on the curve, such that z _i ≠ 0 implies z _w+i-1 = . . . = z _i+1 = 0, like the sliding window binary recodings of integers. It uses a redundant digit set, i.e., an expansion of an integer using this digit set need not be uniquely determined if the syntactical constraints are not enforced. We show that the digit sets described by Solinas, formed by elements of minimal norm in their residue classes, are uniquely determined. Apart from this digit set of minimal norm representatives, other digit sets can be chosen such that all integers can be represented by a width-w non-adjacent form using those digits. We describe an algorithm recognizing admissible digit sets. Results by Solinas and by Blake, Murty, and Xu are generalized. In particular, we introduce two new useful families of digit sets. The first set is syntactically defined. As a consequence of its adoption we can also present improved and streamlined algorithms to perform the precomputations in τ-adic scalar multiplication methods. The latter use an improvement of the computation of sums and differences of points on elliptic curves with mixed affine and López–Dahab coordinates. The second set is suitable for low-memory applications, generalizing an approach started by Avanzi, Ciet, and Sica. It permits to devise a scalar multiplication algorithm that dispenses with the initial precomputation stage and its associated memory space. A suitable choice of the parameters of the method leads to a scalar multiplication algorithm on Koblitz Curves that achieves sublinear complexity in the number of expensive curve operations.     

Computational complexity of the original and extended diophantine Frobenius problem

We deduce the law of nonstationary recursion which makes it possible, for given a primitive set A = {a ₁,...,a _k }, k > 2, to construct an algorithm for finding the set of the numbers outside the additive semigroup generated by A. In particular, we obtain a new algorithm for determining the Frobenius numbers g(a ₁,...,a _k ). The computational complexity of these algorithms is estimated in terms of bit operations. We propose a two-stage reduction of the original primitive set to an equivalent primitive set that enables us to improve complexity estimates in the cases when the two-stage reduction leads to a substantial reduction of the order of the initial set.     

A new algorithm for minimizing makespan, <Emphasis Type="Italic">C</Emphasis><Subscript>max</Subscript>, in blocking flow-shop problem through slowing down the operations

In this paper, a new algorithm with complexity O(nm²) is presented, which finds the optimal makespan, C_max, for a blocking flow-shop problem by slowing down the operations of a no-wait flow-shop problem, F _m ∣no-wait∣C_max, for a given sequence where restriction on the slowing down is committed. However, the problem with performance measure makespan, C_max, in a non-cyclic environment, is a special case of cyclic problem with cycle time, C _t , as its performance measure. This new algorithm is much faster than the previously developed algorithms for cyclical scheduling problems.     

On an Extremal Problem for Poset Dimension

Let f(n) be the largest integer such that every poset on n elements has a 2-dimensional subposet on f(n) elements. What is the asymptotics of f(n)? It is easy to see that f(n) = n ^1/2. We improve the best known upper bound and show f(n) = O (n ^2/3). For higher dimensions, we show \(f_{d}(n)=\O \left (n^{\frac {d}{d + 1}}\right )\), where f _d (n) is the largest integer such that every poset on n elements has a d-dimensional subposet on f _d (n) elements.     

Efficiency of weak greedy algorithms for m-term approximations

We investigate the efficiency of weak greedy algorithms for m-term expansional approximation with respect to quasi-greedy bases in general Banach spaces.We estimate the corresponding Lebesgue constants for the weak thresholding greedy algorithm(WTGA) and weak Chebyshev thresholding greedy algorithm.Then we discuss the greedy approximation on some function classes.For some sparse classes induced by uniformly bounded quasi-greedy bases of L_p,1p∞,we show that the WTGA realizes the order of the best m-term approximation.Finally,we compare the efficiency of the weak Chebyshev greedy algorithm(WCGA) with the thresholding greedy algorithm(TGA) when applying them to quasi-greedy bases in L_p,1≤p∞,by establishing the corresponding Lebesgue-type inequalities.It seems that when p2 the WCGA is better than the TGA.     

Modification of Rissanen’s Method in Linear Memory

The problem of solving a linear system with a Hankel or block-Hankel matrix, as well as Rissanen’s algorithm and its generalization to the block case, are considered. Modifications of these algorithms that use less memory (O(n) against O(n²)).     

On the optimal robust solution of IVPs with noisy information

We investigate the optimal solution of systems of initial-value problems with smooth right-hand side functions f from a Hölder class \(F^{r,\varrho }_{\text {reg}}\), where r ≥ 0 is the number of continuous derivatives of f, and ? ∈ (0, 1] is the Hölder exponent of rth partial derivatives. We consider algorithms that use n evaluations of f, the ith evaluation being corrupted by a noise δ_i of deterministic or random nature. For δ ≥ 0, in the deterministic case the noise δ_i is a bounded vector, ∥δ_i∥≤δ. In the random case, it is a vector-valued random variable bounded in average, (E(∥δ_i∥^q))^1/q ≤ δ, q ∈ [1, + ∞). We point out an algorithm whose L_p error (p ∈ [0, + ∞]) is O(n ^{? (r + ?)} + δ), independently of the noise distribution. We observe that the level n ^{? (r + ?)} + δ cannot be improved in a class of information evaluations and algorithms. For ε > 0, and a certain model of δ-dependent cost, we establish optimal values of n(ε) and δ(ε) that should be used in order to get the error at most ε with minimal cost.     

Boolean Lattices: Ramsey Properties and Embeddings

A subposet Q ^′ of a poset Q is a copy of a poset P if there is a bijection f between elements of P and Q ^′ such that x ≤ y in P iff f(x) ≤ f(y) in Q. For posets P, P ^′, let the poset Ramsey number R(P, P ^′) be the smallest N such that no matter how the elements of the Boolean lattice Q _N are colored red and blue, there is a copy of P with all red elements or a copy of P ^′ with all blue elements. We provide some general bounds on R(P, P ^′) and focus on the situation when P and P ^′ are both Boolean lattices. In addition, we give asymptotically tight bounds for the number of copies of Q _n in Q _N and for a multicolor version of a poset Ramsey number.     

Consistent Digital Rays

Given a fixed origin o in the d-dimensional grid, we give a novel definition of digital rays dig(op) from o to each grid point p. Each digital ray dig(op) approximates the Euclidean line segment \(\overline {op}\) between o and p. The set of all digital rays satisfies a set of axioms analogous to the Euclidean axioms. We measure the approximation quality by the maximum Hausdorff distance between a digital ray and its Euclidean counterpart and establish an asymptotically tight Θ(log?n) bound in the n×n grid. The proof of the bound is based on discrepancy theory and a simple construction algorithm. Without a monotonicity property for digital rays the bound is improved to O(1). Digital rays enable us to define the family of digital star-shaped regions centered at o, which we use to design efficient algorithms for image processing problems.     

On the numerical solution of a minimax control problem with a positional functional

The probabilistic analysis of an approximation algorithm for the minimum-weight m-peripatetic salesman problem with different weight functions of their routes (Hamiltonian cycles) is presented. The time complexity of the algorithm is O(mn ²). It is assumed that the elements of the distance matrix are independent equally distributed random variables with values in an upper unbounded domain [a _n , ∞), where a _n > 0. The analysis is carried out for the example of truncated normal and exponential distributions. Estimates for the relative error and failure probability, as well as conditions for the asymptotic exactness of the algorithm, are found.     

A continuation method for solving symmetric Toeplitz systems

A fast algorithm is proposed for solving symmetric Toeplitz systems. This algorithm continuously transforms the identity matrix into the inverse of a given Toeplitz matrix T. The memory requirements for the algorithm are O(n), and its complexity is O(log κ(T)nlogn), where (T) is the condition number of T. Numerical results are presented that confirm the efficiency of the proposed algorithm.