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.     

Untangling two systems of noncrossing curves

We consider two systems (α₁, …, α_m) and (β₁, …,β_n) of simple curves drawn on a compact two-dimensional surface M with boundary.     

W-Gröbner basis and monomial ideals under polynomial composition

The notion of weakly relatively prime and W-Gröbner basis in K[x ₁, x ₂, …, x _n ] are given. The following results are obtained: for polynomials f ₁, f ₂, …, f _m , \(\{ f_1^{\lambda _1 } ,f_2^{\lambda _2 } ,...,f_m^{\lambda _m } \} \) is a Gröbner basis if and only if f ₁, f ₂, …, f _m are pairwise weakly relatively prime with λ ₁, λ ₂, …, λ _m arbitrary non-negative integers; polynomial composition by Θ = (θ ₁, θ ₂, …, θ _n ) commutes with monomial-Gröbner bases computation if and only if θ ₁, θ ₂, …, θ _m are pairwise weakly relatively prime.     

On the Wick theorem for mixtures of centered Gaussian distributions

We consider centered conditionally Gaussian d-dimensional vectors X with random covariance matrix Ξ having an arbitrary probability distribution law on the set of nonnegative definite symmetric d × d matrices M _d ⁺. The paper deals with the evaluation problem of mean values \( E\left[ {\prod\nolimits_{i = 1}^{2n} {\left( {{c_i},X} \right)} } \right] \) for c _i ∈ ? ^d , i = 1, …, 2n, extending the Wick theorem for a wide class of non-Gaussian distributions. We discuss in more detail the cases where the probability law ?(Ξ) is infinitely divisible, the Wishart distribution, or the inverse Wishart distribution. An example with Ξ \( = \sum\nolimits_{j = 1}^m {{Z_j}{\sum_j}} \), where random variables Z _j , j = 1, …, m, are nonnegative, and Σ _j ∈ M _d ⁺, j = 1, …, m, are fixed, includes recent results from Vignat and Bhatnagar, 2008.     

Linear preservers of row-dense matrices

Let M_m,n be the set of all m × n real matrices. A matrix A ∈ M_m,n is said to be row-dense if there are no zeros between two nonzero entries for every row of this matrix. We find the structure of linear functions T: M_m,n → M_m,n that preserve or strongly preserve row-dense matrices, i.e., T(A) is row-dense whenever A is row-dense or T(A) is row-dense if and only if A is row-dense, respectively. Similarly, a matrix A ∈ M_n,m is called a column-dense matrix if every column of A is a column-dense vector. At the end, the structure of linear preservers (strong linear preservers) of column-dense matrices is found.     

An improvement of the five halves theorem of J. Boardman

Let (M ^m , T) be a smooth involution on a closed smooth m-dimensional manifold and F = ∪ _j=0 ⁿ F ^j (n ≤ m) its fixed point set, where F ^j denotes the union of those components of F having dimension j. The famous Five Halves Theorem of J. Boardman, announced in 1967, establishes that, if F is nonbounding, then m ≤ 5/2n. In this paper we obtain an improvement of the Five Halves Theorem when the top dimensional component of F, F ⁿ , is nonbounding. Specifically, let ω = (i ₁, i ₂, …, i _r ) be a non-dyadic partition of n and s _ω (x ₁, x ₂, …, x _n ) the smallest symmetric polynomial over Z ₂ on degree one variables x ₁, x ₂, …, x _n containing the monomial \(x_1^{i_1 } x_2^{i_2 } \cdots x_r^{i_r }\). Write s _ω (F ⁿ ) ∈ H ⁿ (F ⁿ , Z ₂) for the usual cohomology class corresponding to s _ω (x ₁, x ₂, …, x _n ), and denote by ?(F ⁿ ) the minimum length of a nondyadic partition ω with s _ω (F ⁿ ) ≠ 0 (here, the length of ω = (i ₁, i ₂, …, i _r ) is r). We will prove that, if (M ^m , T) is an involution for which the top dimensional component of the fixed point set, F ⁿ , is nonbounding, then m ≤ 2n + ?(F ⁿ ); roughly speaking, the bound for m depends on the degree of decomposability of the top dimensional component of the fixed point set. Further, we will give examples to show that this bound is best possible.     

Several Generalizations of the Wedderburn-Artin Theorem with Applications

We say that an R-module M is virtually semisimple if each submodule of M is isomorphic to a direct summand of M. A nonzero indecomposable virtually semisimple module is then called a virtually simple module. We carry out a study of virtually semisimple modules and modules which are direct sums of virtually simple modules . Our study provides several natural generalizations of the Wedderburn-Artin Theorem and an analogous to the classical Krull-Schmidt Theorem. Some applications of these theorems are indicated. For instance, it is shown that the following statements are equivalent for a ring R: (i) Every finitely generated left (right) R-module is virtually semisimple; (ii) Every finitely generated left (right) R-module is a direct sum of virtually simple R-modules; (iii) \(R\cong {\prod }_{i = 1}^{k} M_{n_{i}}(D_{i})\) where k,n ₁,…,n _k ∈ ? and each D _i is a principal ideal V-domain; and (iv) Every nonzero finitely generated left R-module can be written uniquely (up to isomorphism and order of the factors) in the form R m ₁ ⊕… ⊕ R m _k where each R m _i is either a simple R-module or a virtually simple direct summand of R.     

On control of the prime spectrum of a finite simple group

The set π(G) of all prime divisors of the order of a finite group G is often called its prime spectrum. It is proved that every finite simple nonabelian group G has sections H ₁, …, H _m of some special form such that π(H ₁)∪…∪π(H _m ) = π(G) and m ≤ 5. Moreover, m ≤ 2 if G is an alternating or classical simple group. In all cases, it is possible to choose the sections H _i so that each of them is a simple nonabelian group, a Frobenius group, or (in one case) a dihedral group. If the above equality holds for a finite group G, then we say that the set {H ₁,…,H _m } controls the prime spectrum of G. We also study some parameter c(G) of finite groups G related to the notion of control.     

Properties of quasi-Boolean function on quasi-Boolean algebra

In this paper, we investigate the following problem: give a quasi-Boolean function Ψ(x ₁, …, x _n ) = (a ∧ C) ∨ (a ₁ ∧ C ₁) ∨ … ∨ (a _p ∧ C _p ), the term (a ∧ C) can be deleted from Ψ(x ₁, …, x _n )? i.e., (a ∧ C) ∨ (a ₁ ∧ C ₁) ∨ … ∨ (a _p ∧ C _p ) = (a ₁ ∧ C ₁) ∨ … ∨ (a _p ∧ C _p )? When a = 1: we divide our discussion into two cases. (1) ?₁(Ψ,C) = ø, C can not be deleted; ?₁(Ψ,C) ≠ ø, if S _i ⁰ ≠ ø (1 ≤ i ≤ q), then C can not be deleted, otherwise C can be deleted. When a = m: we prove the following results: (m∧C)∨(a ₁∧C ₁)∨…∨(a _p ∧C _p ) = (a ₁∧C ₁)∨…∨(a _p ∧C _p ) ? (m ∧ C) ∨ C ₁ ∨ … ∨C _p = C ₁ ∨ … ∨C _p . Two possible cases are listed as follows, (1) ?₂(Ψ,C) = ø, the term (m∧C) can not be deleted; (2) ?₂(Ψ,C) ≠ ø, if (?i ₀) such that \(S'_{i_0 } \) = ø, then (m∧C) can be deleted, otherwise ((m∧C)∨C ₁∨…∨C _q )(v ₁, …, v _n ) = (C ₁ ∨ … ∨ C _q )(v ₁, …, v _n )(?(v ₁, …, v _n ) ∈ L ₃ ⁿ ) ? (C ₁ ^′ ∨ … ∨ C _q ^′ )(u ₁, …, u _q ) = 1(?(u ₁, …, u _q ) ∈ B ₂ ⁿ ).     

On the Exact Maximum Complexity of Minkowski Sums of Polytopes

We present a tight bound on the exact maximum complexity of Minkowski sums of polytopes in ?³. In particular, we prove that the maximum number of facets of the Minkowski sum of k polytopes with m ₁,m ₂,…,m _k facets, respectively, is bounded from above by \(\sum_{1\leq i. Given k positive integers m ₁,m ₂,…,m _k , we describe how to construct k polytopes with corresponding number of facets, such that the number of facets of their Minkowski sum is exactly \(\sum_{1\leq i. When k=2, for example, the expression above reduces to 4m ₁ m ₂?9m ₁?9m ₂+26.     

An algorithm to compute <Emphasis Type="Italic">ω</Emphasis>-primality in a numerical monoid

Let M be a commutative, cancellative, atomic monoid and x a nonunit in M. We define ω(x)=n if n is the smallest positive integer with the property that whenever x∣a ₁???a _t , where each a _i is an atom, there is a T?{1,2,…,t} with |T|≤n such that x∣∏_k∈T a _k . The ω-function measures how far x is from being prime in M. In this paper, we give an algorithm for computing ω(x) in any numerical monoid. Simple formulas for ω(x) are given for numerical monoids of the form 〈n,n+1,…,2n?1〉, where n≥3, and 〈n,n+1,…,2n?2〉, where n≥4. The paper then focuses on the special case of 2-generator numerical monoids. We give a formula for computing ω(x) in this case and also necessary and sufficient conditions for determining when x is an atom. Finally, we analyze the asymptotic behavior of ω(x) by computing \(\lim_{x\rightarrow \infty}\frac{\omega(x)}{x}\).     

The general rigidity result for bundles of <Emphasis Type="Italic">A</Emphasis>-covelocities and <Emphasis Type="Italic">A</Emphasis>-jets

Let M be an m-dimensional manifold and A = D _k ^r /I = R⊕N _A a Weil algebra of height r. We prove that any A-covelocity T _x ^A f ∈ T _x ^A *M, x ∈ M is determined by its values over arbitrary max{width A,m} regular and under the first jet projection linearly independent elements of T _x ^A M. Further, we prove the rigidity of the so-called universally reparametrizable Weil algebras. Applying essentially those partial results we give the proof of the general rigidity result T ^A *M ? T ^r *M without coordinate computations, which improves and generalizes the partial result obtained in Tomá? (2009) from m ≥ k to all cases of m.We also introduce the space J ^A (M,N) of A-jets and prove its rigidity in the sense of its coincidence with the classical jet space J ^r (M,N).     

Word maps and word maps with constants of simple algebraic groups

In the present paper, we consider word maps w: G ^m → G and word maps with constants w _Σ: G ^m → G of a simple algebraic group G, where w is a nontrivial word in the free group F _m of rank m, w _Σ = w ₁ σ ₁ w ₂ ··· w _r σ _r w _{r + 1}, w ₁, …, w _{r + 1} ∈ F _m , w ₂, …, w _r ≠ 1, Σ = {σ ₁, …, σ _r | σ _i ∈ G Z(G)}. We present results on the images of such maps, in particular, we prove a theorem on the dominance of “general” word maps with constants, which can be viewed as an analogue of a well-known theorem of Borel on the dominance of genuine word maps. Besides, we establish a relationship between the existence of unipotents in the image of a word map and the structure of the representation variety R(Γ_w, G) of the group Γ_w = F _m /<w>.     

On Linear Preservers of Two-Sided Gut-Majorization On <Emphasis Type="Bold">M</Emphasis><Subscript><Emphasis Type="Italic">n</Emphasis>,<Emphasis Type="Italic">m</Emphasis></Subscript>

For X, Y ∈ M_n,m it is said that X is gut-majorized by Y, and we write X ?_gutY, if there exists an n-by-n upper triangular g-row stochastic matrix R such that X = RY. Define the relation ~_gut as follows. X ~_gutY if X is gut-majorized by Y and Y is gut-majorized by X. The (strong) linear preservers of ?_gut on ?ⁿ and strong linear preservers of this relation on M_n,m have been characterized before. This paper characterizes all (strong) linear preservers and strong linear preservers of ~_gut on ?ⁿ and M_n,m.     

On <Emphasis Type="Italic">s</Emphasis>-Elementary Super Frame Wavelets and Their Path-Connectedness

A super wavelet of length n is an n-tuple (ψ ₁,ψ ₂,…,ψ _n ) in the product space \(\prod_{j=1}^{n} L^{2}(\mathbb{R})\), such that the coordinated dilates of all its coordinated translates form an orthonormal basis for \(\prod_{j=1}^{n} L^{2} (\mathbb{R})\). This concept is generalized to the so-called super frame wavelets, super tight frame wavelets and super normalized tight frame wavelets (or super Parseval frame wavelets), namely an n-tuple (η ₁,η ₂,…,η _n ) in \(\prod_{j=1}^{n}L^{2} (\mathbb{R})\) such that the coordinated dilates of all its coordinated translates form a frame, a tight frame, or a normalized tight frame for \(\prod_{j=1}^{n} L^{2}(\mathbb{R})\). In this paper, we study the super frame wavelets and the super tight frame wavelets whose Fourier transforms are defined by set theoretical functions (called s-elementary frame wavelets). An m-tuple of sets (E ₁,E ₂,…,E _m ) is said to be τ-disjoint if the E _j ’s are pair-wise disjoint under the 2π-translations. We prove that a τ-disjoint m-tuple (E ₁,E ₂,…,E _m ) of frame sets (i.e., η _j defined by \(\widehat{\eta_{j}}=\frac{1}{\sqrt{2\pi}}\chi_{E_{j}}\) is a frame wavelet for L ²(?) for each j) lead to a super frame wavelet (η ₁,η ₂,…,η _m ) for \(\prod_{j=1}^{m} L^{2} (\mathbb{R})\) where \(\widehat{\eta_{j}}=\frac{1}{\sqrt{2\pi}}\chi_{E_{j}}\). In the case of super tight frame wavelets, we prove that (η ₁,η ₂,…,η _m ), defined by \(\widehat{\eta_{j}}=\frac{1}{\sqrt{2\pi}}\chi_{E_{j}}\), is a super tight frame wavelet for ∏_1≤j≤m L ²(?) with frame bound k ₀ if and only if each η _j is a tight frame wavelet for L ²(?) with frame bound k ₀ and that (E ₁,E ₂,…,E _m ) is τ-disjoint. Denote the set of all τ-disjoint s-elementary super frame wavelets for ∏_1≤j≤m L ²(?) by \(\mathfrak{S}(m)\) and the set of all s-elementary super tight frame wavelets (with the same frame bound k ₀) for ∏_1≤j≤m L ²(?) by \(\mathfrak{S}^{k_{0}}(m)\). We further prove that \(\mathfrak{S}(m)\) and \(\mathfrak{S}^{k_{0}}(m)\) are both path-connected under the ∏_1≤j≤m L ²(?) norm, for any given positive integers m and k ₀.     

Three-machine shop scheduling with partially ordered processing routes

This paper considers the problem of sequencing n jobs in a three-machine shop with the objective of minimising the maximum completion time. The shop consists of three machines, M₁,M₂ and M_{3}. A job is first processed on M₁ and then is assigned either the route (M₂,M_{3}) or the route (M_{3},M₂). Thus, for our model the processing route is given by a partial order of machines, as opposed to the linear order of machines for a job shop, or to an arbitrary sequence of machines for an open shop. The main result is on O(nlog n) time heuristic, which generates a schedule with the makespan that is at most 5/3 times the optimum value.     

The knaster problem: More counterexamples

Given a continuous function\(f:\mathbb{S}^{n - 1} \to \mathbb{R}^m \) andn ?m + 1 pointsp ₁, …,p _{n?m + 1} ε\(p_1 ,...,p_{n - m + 1} \in \mathbb{S}^{n - 1} \), does there exist a rotation ? εSO(n) such thatf(?(p ₁)) = … =f(?(p _n?m+1))? We give a negative answer to this question form = 1 ifn ε {61, 63, 65} orn≥67 and form=2 ifn≥5.     

On (<Emphasis Type="Italic">m</Emphasis>, <Emphasis Type="Italic">n</Emphasis>)-absorbing ideals of commutative rings

Let R be a commutative ring with 1 ≠ 0 and U(R) be the set of all unit elements of R. Let m, n be positive integers such that m > n. In this article, we study a generalization of n-absorbing ideals. A proper ideal I of R is called an (m, n)-absorbing ideal if whenever a ₁?a _m ∈I for a ₁,…, a _m ∈R?U(R), then there are n of the a _i ’s whose product is in I. We investigate the stability of (m, n)-absorbing ideals with respect to various ring theoretic constructions and study (m, n)-absorbing ideals in several commutative rings. For example, in a Bézout ring or a Boolean ring, an ideal is an (m, n)-absorbing ideal if and only if it is an n-absorbing ideal, and in an almost Dedekind domain every (m, n)-absorbing ideal is a product of at most m ? 1 maximal ideals.     

Dual submanifolds in rational homology spheres

Let Σ be a simply connected rational homology sphere. A pair of disjoint closed submanifolds M_+, M_-? Σ are called dual to each other if the complement Σ-M_+ strongly homotopy retracts onto M_- or vice-versa. In this paper, we are concerned with the basic problem of which integral triples(n; m_+, m-) ∈ N~3 can appear, where n = dimΣ-1 and m_± = codim M_±-1. The problem is motivated by several fundamental aspects in differential geometry.(i) The theory of isoparametric/Dupin hypersurfaces in the unit sphere S~(n+1) initiated by′Elie Cartan, where M_± are the focal manifolds of the isoparametric/Dupin hypersurface M ? S~(n+1), and m± coincide with the multiplicities of principal curvatures of M.(ii) The Grove-Ziller construction of non-negatively curved Riemannian metrics on the Milnor exotic spheres Σ,i.e., total spaces of smooth S~3-bundles over S~4 homeomorphic but not diffeomorphic to S~7, where M_± =P_±×_(SO(4))S~3, P → S~4 the principal SO(4)-bundle of Σ and P_± the singular orbits of a cohomogeneity one SO(4) × SO(3)-action on P which are both of codimension 2.Based on the important result of Grove-Halperin, we provide a surprisingly simple answer, namely, if and only if one of the following holds true:· m_+ = m_-= n;· m_+ = m_-=1/3n ∈ {1, 2, 4, 8};· m_+ = m_-=1/4n ∈ {1, 2};· m_+ = m_-=1/6n ∈ {1, 2};·n/(m_++m_-)= 1 or 2, and for the latter case, m_+ + m_-is odd if min(m_+, m_-)≥2.In addition, if Σ is a homotopy sphere and the ratio n/(m_++m_-)= 2(for simplicity let us assume 2 m_- m_+),we observe that the work of Stolz on the multiplicities of isoparametric hypersurfaces applies almost identically to conclude that, the pair can be realized if and only if, either(m_+, m_-) =(5, 4) or m_+ + m_-+ 1 is divisible by the integer δ(m_-)(see the table on Page 1551), which is equivalent to the existence of(m_--1) linearly independent vector fields on the sphere S~(m_++m_-)by Adams' celebrated work. In contrast, infinitely many counterexamples are given if Σ is a rational homology sphere.     

Two-stage flexible flow shop scheduling subject to fixed job sequences

This paper investigates the scheduling problem in a two-stage flexible flow shop, which consists of m stage-1 parallel dedicated machines and a stage-2 bottleneck machine, subject to the condition that n _l jobs per type l∈{1, …, m} are processed in a fixed sequence. Four regular performance metrics, including the total completion time, the maximum lateness, the total tardiness, and the number of tardy jobs, are considered. For each considered objective function, we aim to determine an optimal interleaving processing sequence of all jobs coupled with their starting times on the stage-2 bottleneck machine. The problem under study is proved to be strongly NP-hard. An O(m²Π_l=1 ^m n _l ²) dynamic programming algorithm coupled with numerical experiments is presented.