A Lexicographic 0.5-Approximation Algorithm for the Multiple Knapsack Problem

We present a 0.5-approximation algorithm for the Multiple Knapsack Problem (MKP). The algorithm uses the ordering of knapsacks according to the nondecreasing of size and the two orderings of items: in nonincreasing utility order and in nonincreasing order of the utility/size ratio. These orderings create two lexicographic orderings on A × B (here A is the set of knapsacks and B is the set of indivisible items). Based on each of these lexicographic orderings, the algorithm creates a feasible solution to the MKP by looking through the pairs (a, b) ∈ A × B in the corresponding order and placing item b into knapsack a if this item is not placed yet and there is enough free space in the knapsack. The algorithm chooses the best of the two obtained solutions. This algorithm is 0.5-approximate and has runtime O(mn) (without sorting), where mand n are the sizes of A and B correspondingly.     

Multi-period empty container repositioning with stochastic demand and lost sales

This paper considers repositioning empty containers between multi-ports over multi-periods with stochastic demand and lost sales. The objective is to minimize the total operating cost including container-holding cost, stockout cost, importing cost and exporting cost. First, we formulate the single-port case as an inventory problem over a finite horizon with stochastic import and export of empty containers. The optimal policy for period n is characterized by a pair of critical points (A _n , S _n ), that is, importing empty containers up to A _n when the number of empty containers in the port is fewer than A _n ; exporting empty containers down to S _n when the number of empty containers in the port is more than S _n ; and doing nothing, otherwise. A polynomial-time algorithm is developed to determine the two thresholds, that is, A _n and S _n , for each period. Next, we formulate the multi-port problem and determine a tight lower bound on the cost function. On the basis of the two-threshold optimal policy for a single port, a polynomial-time algorithm is developed to find an approximate repositioning policy for multi-ports. Simulation results show that the proposed approximate repositioning algorithm performs very effectively and efficiently.     

A stability result using the matrix norm to bound the permanent

We prove a stability version of a general result that bounds the permanent of a matrix in terms of its operator norm. More specifically, suppose A is an n × n matrix over C (resp. R), and let P denote the set of n × n matrices over C (resp. R) that can be written as a permutation matrix times a unitary diagonal matrix. Then it is known that the permanent of A satisfies |per(A)| ≤ ||A|| ⁿ ₂ with equality iff A/||A||₂ ∈ P (where ||A||₂ is the operator 2-norm of A). We show a stability version of this result asserting that unless A is very close (in a particular sense) to one of these extremal matrices, its permanent is exponentially smaller (as a function of n) than ||A|| ⁿ ₂. In particular, for any fixed α, β > 0, we show that |per(A)| is exponentially smaller than ||A|| ⁿ ₂ unless all but at most αn rows contain entries of modulus at least ||A||₂(1?β).     

Group distance magic and antimagic graphs

Given a graph G with n vertices and an Abelian group A of order n, an A-distance antimagic labelling of G is a bijection from V (G) to A such that the vertices of G have pairwise distinct weights, where the weight of a vertex is the sum (under the operation of A) of the labels assigned to its neighbours. An A-distance magic labelling of G is a bijection from V (G) to A such that the weights of all vertices of G are equal to the same element of A. In this paper we study these new labellings under a general setting with a focus on product graphs. We prove among other things several general results on group antimagic or magic labellings for Cartesian, direct and strong products of graphs. As applications we obtain several families of graphs admitting group distance antimagic or magic labellings with respect to elementary Abelian groups, cyclic groups or direct products of such groups.     

Variable interval sampling in economical designs for online process control of attributes with misclassification errors

Online process control consists of inspecting a single item at every mth items produced, where m is an integer greater than two. Based on the results of the inspection, one decides if the process is in-control (the fraction of conforming item is p₁—state I) or out-of-control (the fraction of conforming item is p₂—state II). If the inspected item is non-conforming, the process is designated as out-of-control and production is stopped for possible adjustment; otherwise, production goes on. In this paper, a contribution to online process control is presented, where the inspection system is considered to be subject to classification errors. After every adjustment, the sampling interval is L units (L?m), and in the case of non-adjustment, the sampling interval is m units. The expression for the average cost per produced item is calculated, and optimum parameters (the sampling intervals L and m) are obtained by a direct search. The procedure is illustrated by a numerical example.     

Palindromic widths of nilpotent and wreath products

We prove that the nilpotent product of a set of groups A ₁,…,A _s has finite palindromic width if and only if the palindromic widths of A _i ,i=1,…,s,are finite. We give a new proof that the commutator width of F _n ?K is infinite, where F _n is a free group of rank n≥2 and K is a finite group. This result, combining with a result of Fink [9] gives examples of groups with infinite commutator width but finite palindromic width with respect to some generating set.     

Tensor products of tilting modules

We consider whether the tilting properties of a tilting A-module T and a tilting B-module T′ can convey to their tensor product T ? T′: The main result is that T ? T′ turns out to be an (n + m)-tilting A ? B-module, where T is an m-tilting A-module and T′ is an n-tilting B-module.     

On the structure of finite groups isospectral to an alternating group

It is proved that every finite group isospectral to an alternating group A _n of degree n greater than 21 has a chief factor isomorphic to an alternating group A _k , where k ≤ n and the half-interval (k, n] contains no primes.     

Note: A conjecture on partitions of groups

We conjecture that every infinite group G can be partitioned into countably many cells \(G = \bigcup\limits_{n \in \omega } {A_n }\) such that cov(A _n A _n ^?1 ) = |G| for each n ∈ ω Here cov(A) = min{|X|: X} ? G, G = X A}. We confirm this conjecture for each group of regular cardinality and for some groups (in particular, Abelian) of an arbitrary cardinality.     

The Number of <Emphasis Type="Italic">k</Emphasis>-Sumsets in an Abelian Group

Let G be an abelian group of order n. The sum of subsets A₁,...,A_k of G is defined as the collection of all sums of k elements from A₁,...,A_k; i.e., A₁ + A₂ + · · · + A_k = {a₁ + · · · + a_k | a₁ ∈ A₁,..., a_k ∈ A_k}. A subset representable as the sum of k subsets of G is a k-sumset. We consider the problem of the number of k-sumsets in an abelian group G. It is obvious that each subset A in G is a k-sumset since A is representable as A = A₁ + · · · + A_k, where A₁ = A and A₂ = · · · = A_k = {0}. Thus, the number of k-sumsets is equal to the number of all subsets of G. But, if we introduce a constraint on the size of the summands A₁,...,A_k then the number of k-sumsets becomes substantially smaller. A lower and upper asymptotic bounds of the number of k-sumsets in abelian groups are obtained provided that there exists a summand A_i such that |A_i| = n log^qn and |A₁ +· · ·+ A_i-1 + A_i+1 + · · ·+A_k| = n log^qn, where q = -1/8 and i ∈ {1,..., k}.     

Mortality Risk and Life Expectancy

Changing the mortality risks we face would change human life expectancy. As a special case, one could imagine adding a fixed increment R to all the age-specific mortality rates from age zero upwards. For this case we seek a constant K(A) such that K(A) x R approximates the resulting change in life expectancy remaining at age A, at least for small values of R. The formula for K(A) derived here corrects a heuristic argument that appeared in JORS earlier. An estimate of K(0) suggests that the permanent addition of a one-in-a-million risk at each year of life would reduce life expectancy at birth by about 1 day—a useful fact for risk communication.     

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.     

Characterization of 2-Local Derivations and Local Lie Derivations on Some Algebras

We prove that each 2-local derivation from the algebra M_n(A ) (n > 2) into its bimodule M_n(M) is a derivation, where A is a unital Banach algebra and M is a unital A -bimodule such that each Jordan derivation from A into M is an inner derivation, and that each 2-local derivation on a C*-algebra with a faithful traceable representation is a derivation. We also characterize local and 2-local Lie derivations on some algebras such as von Neumann algebras, nest algebras, the Jiang–Su algebra, and UHF algebras.     

Multiset combinatorial batch codes

Batch codes, first introduced by Ishai, Kushilevitz, Ostrovsky, and Sahai, mimic a distributed storage of a set of n data items on m servers, in such a way that any batch of k data items can be retrieved by reading at most some t symbols from each server. Combinatorial batch codes, are replication-based batch codes in which each server stores a subset of the data items. In this paper, we propose a generalization of combinatorial batch codes, called multiset combinatorial batch codes (MCBC), in which n data items are stored in m servers, such that any multiset request of k items, where any item is requested at most r times, can be retrieved by reading at most t items from each server. The setup of this new family of codes is motivated by recent work on codes which enable high availability and parallel reads in distributed storage systems. The main problem under this paradigm is to minimize the number of items stored in the servers, given the values of n, m, k, r, t, which is denoted by N(n, k, m, t; r). We first give a necessary and sufficient condition for the existence of MCBCs. Then, we present several bounds on N(n, k, m, t; r) and constructions of MCBCs. In particular, we determine the value of N(n, k, m, 1; r) for any \(n\ge \left\lfloor \frac{k-1}{r}\right\rfloor {m\atopwithdelims ()k-1}-(m-k+1)A(m,4,k-2)\), where \(A(m,4,k-2)\) is the maximum size of a binary constant weight code of length m, distance four and weight \(k-2\). We also determine the exact value of N(n, k, m, 1; r) when \(r\in \{k,k-1\}\) or \(k=m\).     

The real symmetric matrices of odd order with a P-set of maximum size

Suppose that A is a real symmetric matrix of order n. Denote by m_A(0) the nullity of A. For a nonempty subset α of {1, 2,..., n}, let A(α) be the principal submatrix of A obtained from A by deleting the rows and columns indexed by α. When m_A(α)(0) = m_A(0)+|α|, we call α a P-set of A. It is known that every P-set of A contains at most ?n/2? elements. The graphs of even order for which one can find a matrix attaining this bound are now completely characterized. However, the odd case turned out to be more difficult to tackle. As a first step to the full characterization of these graphs of odd order, we establish some conditions for such graphs G under which there is a real symmetric matrix A whose graph is G and contains a P-set of size (n ? 1)/2.     

Deterministic hierarchical substitution inventory models

In this paper, we consider a deterministic nested substitution problem where there are multiple products which can be substituted one for the other, if necessary, at a certain cost. We consider the case when there are n products, and product j can substitute products j + 1,…,n at certain costs. The trade-off is the cost of storing products (for example, customised products) at a higher inventory holding stage versus the cost of transferring downwards from a lower inventory holding cost (generic product) stage. The standard approach to solving the problem yields an intractable formulation, but by reformulating the problem to determine the optimal run-out times, we are able to determine the optimal order and substitution quantities. Numerical examples showing the effect of various system parameters on the optimal order and substitution policy are also presented.     

Certain pairs of irreducible characters of the groups <Emphasis Type="Italic">S</Emphasis><Subscript><Emphasis Type="Italic">n</Emphasis></Subscript>

The investigation of the pairs of irreducible characters of the symmetric group S _n that have the same set of roots in one of the sets A _n and S _n ? A _n is continued. All such pairs of irreducible characters of the group S _n are found in the case when the least of the main diagonal’s lengths of the Young diagrams corresponding to these characters does not exceed 2. Some arguments are obtained for the conjecture that alternating groups A _n have no pairs of semiproportional irreducible characters.     

Under-recurrence in the Khintchine recurrence theorem

The Khintchine recurrence theorem asserts that in a measure preserving system, for every set A and ε > 0, we have μ(A ∩ T^?nA) ≥ μ(A)² ? ε for infinitely many n ∈ N. We show that there are systems having underrecurrent sets A, in the sense that the inequality μ(A ∩ T^?nA) < μ(A)² holds for every n ∈ N. In particular, all ergodic systems of positive entropy have under-recurrent sets. On the other hand, answering a question of V. Bergelson, we show that not all mixing systems have under-recurrent sets. We also study variants of these problems where the previous strict inequality is reversed, and deduce that under-recurrence is a much more rare phenomenon than over-recurrence. Finally, we study related problems pertaining to multiple recurrence and derive some interesting combinatorial consequences.     

Hochschild Cohomology of Deformation Quantizations over ℤ/<Emphasis Type="Italic">p</Emphasis><Superscript><Emphasis Type="Italic">n</Emphasis></Superscript>ℤ

Let A ₁ be an Azumaya algebra over a smooth affine symplectic variety X over Spec F _p , where p is an odd prime. Let A be a deformation quantization of A ₁ over the p-adic integers. In this note we show that for all n ≥ 1, the Hochschild cohomology of A/p ⁿ A is isomorphic to the de Rham-Witt complex \(W_{n}{\Omega }^{\ast }_{X}\) of X over \(\mathbb {Z}/p^{n}\mathbb {Z}\). We also compute the center of deformations of certain affine Poisson varieties over F _p .     

Possible isolation number of a matrix over nonnegative integers

Let ?₊ be the semiring of all nonnegative integers and A an m × n matrix over ?₊. The rank of A is the smallest k such that A can be factored as an m × k matrix times a k×n matrix. The isolation number of A is the maximum number of nonzero entries in A such that no two are in any row or any column, and no two are in a 2 × 2 submatrix of all nonzero entries. We have that the isolation number of A is a lower bound of the rank of A. For A with isolation number k, we investigate the possible values of the rank of A and the Boolean rank of the support of A. So we obtain that the isolation number and the Boolean rank of the support of a given matrix are the same if and only if the isolation number is 1 or 2 only. We also determine a special type of m×n matrices whose isolation number is m. That is, those matrices are permutationally equivalent to a matrix A whose support contains a submatrix of a sum of the identity matrix and a tournament matrix.