On the bin packing problem with a fixed number of object weights

We consider a bin packing problem where the number of different object weights is fixed to C. We analyze a simple approximate approach and show that it leads to an asymptotically exact polynomial algorithm with absolute error 0 if C = 2, at most 1 if 1 < C ? 6, and at most 1 + ⌊(C − 1)/3⌋ if C > 6. A consequence of our analysis is a new upper bound on the gap between the optimal value of the problem at hand and the round-up of the optimal value of the linear relaxation of its Gilmore–Gomory formulation.     

Bounding the gap between extremal Laplacian eigenvalues of graphs

Let G be a graph whose Laplacian eigenvalues are 0 = λ₁ ? λ₂ ? ? ? λ_n. We investigate the gap (expressed either as a difference or as a ratio) between the extremal non-trivial Laplacian eigenvalues of a connected graph (that is λ_n and λ₂). This gap is closely related to the average density of cuts in a graph. We focus here on the problem of bounding the gap from below.     

Batch delivery scheduling with batch delivery cost on a single machine

We consider a scheduling problem in which n independent and simultaneously available jobs are to be processed on a single machine. The jobs are delivered in batches and the delivery date of a batch equals the completion time of the last job in the batch. The delivery cost depends on the number of deliveries. The objective is to minimize the sum of the total weighted flow time and delivery cost. We first show that the problem is strongly NP-hard. Then we show that, if the number of batches is B, the problem remains strongly NP-hard when B ? U for a variable U ? 2 or B ? U for any constant U ? 2. For the case of B ? U, we present a dynamic programming algorithm that runs in pseudo-polynomial time for any constant U ? 2. Furthermore, optimal algorithms are provided for two special cases: (i) jobs have a linear precedence constraint, and (ii) jobs satisfy the agreeable ratio assumption, which is valid, for example, when all the weights or all the processing times are equal.     

Bipanconnectivity of faulty hypercubes with minimum degree

In this paper, we consider the conditionally faulty hypercube Q_n with n ? 2 where each vertex of Q_n is incident with at least m fault-free edges, 2 ? m ? n − 1. We shall generalize the limitation m ? 2 in all previous results of edge-bipancyclicity. We also propose a new edge-fault-tolerant bipanconnectivity called k-edge-fault-tolerant bipanconnectivity. A bipartite graph is k-edge-fault-tolerant bipanconnected if G − F remains bipanconnected for any F ⊂ E(G) with ∣F∣ ? k. For every integer m, under the same hypothesis, we show that Q_n is (n − 2)-edge-fault-tolerant edge-bipancyclic and bipanconnected, and the results are optimal with respect to the number of edge faults tolerated. This not only improves some known results on edge-bipancyclicity and bipanconnectivity of hypercubes, but also simplifies the proof.     

On the Hermitian positive definite solutions of nonlinear matrix equation X + A∗XA = Q

Nonlinear matrix equation X^s + A∗X^−tA = Q, where A, Q are n × n complex matrices with Q Hermitian positive definite, has widely applied background. In this paper, we consider the Hermitian positive definite solutions of this matrix equation with two cases: s ? 1, 0 < t ? 1 and 0 < s ? 1, t ? 1. We derive necessary conditions and sufficient conditions for the existence of Hermitian positive definite solutions for the matrix equation and obtain some properties of the solutions. We also propose iterative methods for obtaining the extremal Hermitian positive definite solution of the matrix equation. Finally, we give some numerical examples to show the efficiency of the proposed iterative methods.     

Alexandrov’s inequality and conjectures on some Toeplitz matrices

We study determinant inequalities for certain Toeplitz-like matrices over C. For fixed n and N ? 1, let Q be the n × (n + N − 1) zero-one Toeplitz matrix with Q_ij = 1 for 0 ? j − i ? N − 1 and Q_ij = 0 otherwise. We prove that det(QQ^∗) is the minimum of det(RR^∗) over all complex matrices R with the same dimensions as Q satisfying ∣R_ij∣ ? 1 whenever Q_ij = 1 and R_ij = 0 otherwise. Although R has a Toeplitz-like band structure, it is not required to be actually Toeplitz. Our proof involves Alexandrov’s inequality for polarized determinants and its generalizations. This problem is motivated by Littlewood’s conjecture on the minimum 1-norm of N-term exponential sums on the unit circle. We also discuss polarized Bazin-Reiss-Picquet identities, some connections with k-tree enumeration, and analogous conjectured inequalities for the elementary symmetric functions of QQ^∗.     

Generalized Gaussian quadrature rules over two-dimensional regions with linear sides

This paper presents a generalized Gaussian quadrature method for numerical integration over triangular, parallelogram and quadrilateral elements with linear sides. In order to derive the quadrature rule, a general transformation of the regions, R₁ = {(x, y)∣a ? x ? b, g(x) ? y ? h(x)} and R₂ = {(x, y)∣a ? y ? b, g(y) ? x ? h(y)}, where g(x), h(x), g(y) and h(y) are linear functions, is given from (x, y) space to a square in (ξ, η) space, S: {(ξ, η)∣0 ? ξ ? 1, 0 ? η ? 1}. Generlized Gaussian quadrature nodes and weights introduced by Ma et.al. in 1997 are used in the product formula presented in this paper to evaluate the integral over S, as it is proved to give more accurate results than the classical Gauss Legendre nodes and weights. The method can be used to integrate a wide class of functions including smooth functions and functions with end-point singularities, over any two-dimensional region, bounded by linear sides. The performance of the method is illustrated for different functions over different two-dimensional regions with numerical examples.     

Fault-tolerant edge and vertex pancyclicity in alternating group graphs

In [J.-M. Chang, J.-S. Yang. Fault-tolerant cycle-embedding in alternating group graphs, Appl. Math. Comput. 197 (2008) 760-767] the authors claim that every alternating group graph AG_n is (n − 4)-fault-tolerant edge 4-pancyclic. Which means that if the number of faults ∣F∣ ? n − 4, then every edge in AG_n − F is contained in a cycle of length ?, for every 4 ? ? ? n!/2 − ∣F∣. They also claim that AG_n is (n − 3)-fault-tolerant vertex pancyclic. Which means that if ∣F∣ ? n − 3, then every vertex in AG_n − F is contained in a cycle of length ?, for every 3 ? ? ? n!/2 − ∣F∣. Their proofs are not complete. They left a few important things unexplained. In this paper we fulfill these gaps and present another proofs that AG_n is (n − 4)-fault-tolerant edge 4-pancyclic and (n − 3)-fault-tolerant vertex pancyclic.     

The impact of smooth W-grids in the numerical solution of singular perturbation two-point boundary value problems

This paper develops a semi-analytic technique for generating smooth nonuniform grids for the numerical solution of singularly perturbed two-point boundary value problems. It is based on the usual idea of mapping a uniform grid to the desired nonuniform grid. We introduce the W-grid, which depends on the perturbation parameter ? ? 1. For problems on [0, 1] with a boundary layer at one end point, the local mesh width h_i = x_i+1 − x_i, with 0 = x₀ < x₁ < ? < x_N = 1, is condensed at either 0 or 1. Two simple 2nd order finite element and finite difference methods are combined with the new mesh, and computational experiments demonstrate the advantages of the smooth W-grid compared to the well-known piecewise uniform Shishkin mesh. For small ?, neither the finite difference method nor the finite element method produces satisfactory results on the Shishkin mesh. By contrast, accuracy is vastly improved on the W-grid, which typically produces the nominal 2nd order behavior in L², for large as well as small values of N, and over a wide range of values of ?. We conclude that the smoothness of the mesh is of crucial importance to accuracy, efficiency and robustness.     

New ideas for decomposing nonlinearities in differential equations

In this paper we consider the decomposition for the nonlinearity in a differential equation for the solution by decomposition. By analyzing and transforming the Taylor expansion of the nonlinearity about the initial solution component, the decomposition of the nonlinearity is converted to the partitions of the solution sets for a class of Diophantine equations. This conversion simplifies the discussion and presents a new idea for decompositions. We enumerate five types of partitions and their corresponding decomposition polynomials. Each of the last four types contains infinitely many kinds of decomposition polynomials in the form of finite sums. In Types 2, 3 and 4, there is a parameter q and each value of q corresponds to a class of decomposition polynomials. In Type 5, each positive integer sequence {c_j} satisfying 1 = c₁ ? c₂ ? ? and j ? c_j for j = 2, 3, … corresponds to a class of decomposition polynomials. Four classes of the Adomian polynomials [R. Rach, A new definition of the Adomian polynomials, Kybernetes 37 (2008) 910-955] are derived as particular cases.     

Eigenvalue inequalities for convex and log-convex functions

We give a matrix version of the scalar inequality f(a + b) ? f(a) + f(b) for positive concave functions f on [0, ∞). We show that Choi’s inequality for positive unital maps and operator convex functions remains valid for monotone convex functions at the cost of unitary congruences. Some inequalities for log-convex functions are presented and a new arithmetic-geometric mean inequality for positive matrices is given. We also point out a simple proof of the Bhatia-Kittaneh arithmetic-geometric mean inequality.     

Inequalities between ∥f(A + B)∥ and ∥f(A) + f(B)∥

The conjecture posed by Aujla and Silva [J.S. Aujla, F.C. Silva, Weak majorization inequalities and convex functions, Linear Algebra Appl. 369 (2003) 217-233] is proved. It is shown that for any m-tuple of positive-semidefinite n × n complex matrices A_j and for any non-negative convex function f on [0, ∞) with f(0) = 0 the inequality ?f(A₁) + f(A₂) + ? + f(A_m)? ? ? f(A₁ + A₂ + ? + A_m)? holds for any unitarily invariant norm ? · ?. It is also proved that ?f(A₁) + f(A₂) + ? + f(A_m)? ? f(?A₁ + A₂ + ? + A_m?), where f is a non-negative concave function on [0, ∞) and ? · ? is normalized.     

Strong linear preservers of rank reverse permutability on triangular matrices

Let F be a field with ∣F∣ > 2 and T_n(F) be the set of all n × n upper triangular matrices, where n ? 2. Let k ? 2 be a given integer. A k-tuple of matrices A₁, …, A_k ∈ T_n(F) is called rank reverse permutable if rank(A₁ A₂ ? A_k) = rank(A_k A_k−1 ? A₁). We characterize the linear maps on T_n(F) that strongly preserve the set of rank reverse permutable matrix k-tuples.     

Some notes on graphs whose index is close to 2

We consider two classes of graphs: (i) trees of order n and diameter d =n − 3 and (ii) unicyclic graphs of order n and girth g = n − 2. Assuming that each graph within these classes has two vertices of degree 3 at distance k, we order by the index (i.e. spectral radius) the graphs from (i) for any fixed k (1 ? k ? d − 2), and the graphs from (ii) independently of k.     

Some trace formulae involving the split sequences of a Leonard pair

Let K denote a field, and let V denote a vector space over K with finite positive dimension. We consider a pair of linear transformations A : V → V and A^∗ : V → V that satisfy (i) and (ii) below:

(i)

There exists a basis for V with respect to which the matrix representing A is irreducible tridiagonal and the matrix representing A^∗ is diagonal.

(ii)

There exists a basis for V with respect to which the matrix representing A^∗ is irreducible tridiagonal and the matrix representing A is diagonal.

We call such a pair a Leonard pair on V. Let diag(θ₀, θ₁, … , θ_d) denote the diagonal matrix referred to in (ii) above and let denote the diagonal matrix referred to in (i) above. It is known that there exists a basis u₀, u₁, … , u_d for V and there exist scalars ?₁, ?₂, … , ?_d in K such that Au_i = θ_iu_i + u_i+1 (0 ? i ? d − 1), Au_d = θ_du_d, , . The sequence ?₁, ?₂, … , ?_d is called the first split sequence of the Leonard pair. It is known that there exists a basis v₀, v₁, … , v_d for V and there exist scalars ?₁, ?₂, … , ?_d in K such that Av_i = θ_d−iv_i + v_i+1 (0 ? i ? d − 1),Av_d = θ₀v_d, , . The sequence ?₁, ?₂, … , ?_d is called the second split sequence of the Leonard pair. We display some attractive formulae for the first and second split sequence that involve the trace function.     

Characterization of the trace by monotonicity inequalities

Let ?be a positive linear functional on the algebra of n × n complex matrices and p be a number greater than 1. The main result of the paper says that if for any pair A, B of positive semi-definite n × n matrices with A ? B the inequality ?(A^p) ? ?(B^p) holds true, then ?is a nonnegative scalar multiple of the trace.     

Finite projective planes admitting a projective linear group PSL (2, q)

Let S be a projective plane, and let G?Aut(S) and PSL(2, q) ? G ? PΓL(2, q) with q > 3. If G acts point-transitively on S, then q = 7 and S is of order 2.     

Precise Spectral Asymptotics for the Dirichlet Problem − u″(t) + g(u(t)) = λsinu(t)

We consider the nonlinear eigenvalue problem on an interval−u″(t)+g(u(t))=λsinu(t),u(t)>0,t∈I:=(−T,T),u(±T)=0,where λ > 0 is a parameter and T > 0 is a constant. It is known that if λ ? 1, then the corresponding solution has boundary layers. In this paper, we characterize λ by the boundary layers of the solution when λ ? 1 from a variational point of view. To this end, we parameterize a solution pair (λ, u) by a new parameter 0 < ?< T, which characterizes the boundary layers of the solution, and establish precise asymptotic formulas for λ(?) with exact second term as ? → 0. It turns out that the second term is a constant which is explicitly determined by the nonlinearity g.