Indeterminacy Criteria for the Stieltjes Matrix Moment Problem

In this paper, we obtain criteria for the indeterminacy of the Stieltjes matrix moment problem. We obtain explicit formulas for Stieltjes parameters and study the multiplicative structure of the resolvent matrix. In the indeterminate case, we study the analytic properties of the resolvent matrix of the moment problem. We describe the set of all matrix functions associated with the indeterminate Stieltjes moment problem in terms of linear fractional transformations over Stieltjes pairs.     

Step-by-step solving of ordered interpolation problem for stieltjes functions

We investigate a step-by-step solving of ordered generalized interpolation problems for Stieltjes matrix functions and obtain a multiplicative representation for the sequence of resolvent matrices. Thematrix factors inmultiplicative representations of the resolventmatrices are expressed through the Schur–Stieltjes parameters, for which we obtain explicit formulas and give an algorithm of step-by-step solving of Stieltjes type interpolation problems. As examples, we consider step-by-step solutions of the Stieltjes matrix moment problem and the problems by Nevanlinna–Pick and Caratheodory.     

Log-convex and Stieltjes moment sequences

We show that Stieltjes moment sequences are infinitely log-convex, which parallels a famous result that (finite) Pólya frequency sequences are infinitely log-concave. We introduce the concept of q-Stieltjes moment sequences of polynomials and show that many well-known polynomials in combinatorics are such sequences. We provide a criterion for linear transformations and convolutions preserving Stieltjes moment sequences. Many well-known combinatorial sequences are shown to be Stieltjes moment sequences in a unified approach and therefore infinitely log-convex, which in particular settles a conjecture of Chen and Xia about the infinite log-convexity of the Schröder numbers. We also list some interesting problems and conjectures about the log-convexity and the Stieltjes moment property of the (generalized) Apéry numbers.     

The Moment Problem Associated with the q -Laguerre Polynomials

Abstract. We consider the indeterminate Stieltjes moment problem associated with the q -Laguerre polynomials. A transformation of the set of solutions, which has all the classical solutions as fixed points, is established and we present a method to construct, for instance, continuous singular solutions. The connection with the moment problem associated with the Stieltjes—Wigert polynomials is studied; we show how to come from q -Laguerre solutions to Stieltjes—Wigert solutions by letting the parameter α —> ∞ , and we explain how to lift a Stieltjes—Wigert solution to a q -Laguerre solution at the level of Pick functions. Based on two generating functions, expressions for the four entire functions from the Nevanlinna parametrization are obtained.     

Nevanlinna–Pick Problem for Stieltjes Matrix Functions

We consider the Nevanlinna–Pick interpolation problem for Stieltjes matrix functions. We obtain two criteria for the indeterminacy of the Nevanlinna–Pick problem with infinitely many interpolation nodes. In the indeterminate case, we describe the general solution of the Nevanlinna–Pick problem in terms of fractional-linear transformations.     

Bi-criteria scheduling problems: Number of tardy jobs and maximum weighted tardiness

Consider a single machine and a set of n jobs that are available for processing at time 0. Job j has a processing time p_j, a due date d_j and a weight w_j. We consider bi-criteria scheduling problems involving the maximum weighted tardiness and the number of tardy jobs. We give NP-hardness proofs for the scheduling problems when either one of the two criteria is the primary criterion and the other one is the secondary criterion. These results answer two open questions posed by Lee and Vairaktarakis in 1993. We consider complexity relationships between the various problems, give polynomial-time algorithms for some special cases, and propose fast heuristics for the general case. The effectiveness of the heuristics is measured by empirical study. Our results show that one heuristic performs extremely well compared to optimal solutions.     

Rational matrix functions associated with the Nevanlinna-Pick problem in the class <Emphasis Type="Italic">S</Emphasis>[<Emphasis Type="Italic">a,b</Emphasis>] and orthogonal on a compact interval

We consider the interpolation Nevanlinna-Pick problem with infinitely many interpolation nodes in the class S[a, b] and rational matrix functions associated with this problem and orthogonal on the segment [a, b]. We obtain a criterion of complete indeterminacy of the Nevanlinna-Pick problem in terms of orthogonal rational matrix functions. __________ Translated from Ukrains’kyi Matematychnyi Zhurnal, Vol. 59, No. 6, pp. 764–770, June, 2007.     

Boundary value problem with normal derivatives for a higher-order elliptic equation on the plane

For an elliptic operator of order 2l with constant (and only leading) real coefficients, we consider a boundary value problem in which the normal derivatives of order (k _j ?1), j = 1,..., l, where 1 ≤ k ₁ < ··· < k _l, are specified. It becomes the Dirichlet problem for kj = j and the Neumann problem for k _j = j + 1. We obtain a sufficient condition for the Fredholm property of which problem and derive an index formula.     

The optimal solution set of the interval linear programming problems

Several methods exist for solving the interval linear programming (ILP) problem. In most of these methods, we can only obtain the optimal value of the objective function of the ILP problem. In this paper we determine the optimal solution set of the ILP as the intersection of some regions, by the best and the worst case (BWC) methods, when the feasible solution components of the best problem are positive. First, we convert the ILP problem to the convex combination problem by coefficients 0 ≤ λ _j , μ _ij , μ _i  ≤ 1, for i = 1, 2, . . . , m and j = 1, 2, . . . , n. If for each i, j, μ _ij  = μ _i  = λ _j  = 0, then the best problem has been obtained (in case of minimization problem). We move from the best problem towards the worst problem by tiny variations of λ _j , μ _ij and μ _i from 0 to 1. Then we solve each of the obtained problems. All of the optimal solutions form a region that we call the optimal solution set of the ILP. Our aim is to determine this optimal solution set by the best and the worst problem constraints. We show that some theorems to validity of this optimal solution set.     

On the Nevanlinna-Pick interpolation problem for generalized stieltjes functions

The solutions of the Nevanlinna-Pick interpolation problem for generalized Stieltjes matrix functions are parametrized via a fractional linear transformation over a subset of the class of classical Stieltjes functions. The fractional linear transformation of some of these functions may have a pole in one or more of the interpolation points, hence not all Stieltjes functions can serve as a parameter. The set of excluded parameters is characterized in terms of the two related Pick matrices.Dedicated to the memory of M. G. Kreîn     

Structure of Stieltjes classes of moment-equivalent probability laws

A Stieltjes class is a one-parameter family of moment-equivalent distribution functions constructed by modulation of a given indeterminate distribution function F, called the center of the class. Members of a Stieltjes class are mutually absolutely continuous, and conversely, any pair of moment-equivalent and mutually absolutely continuous distribution functions can be joined by a Stieltjes class. The center of a Stieltjes class is an equally weighted mixture of its extreme members, and this places restrictions on which distributions can belong to a Stieltjes class with a given center. The lognormal law provides interesting illustrations of the general ideas. In particular, it is possible for two moment equivalent infinitely divisible distributions to be joined by a Stieltjes class, and random scaling can be used to construct new Stieltjes classes from a given Stieltjes class.     

An optimal online algorithm for two-machine open shop preemptive scheduling with bounded processing times

This paper deals with a two-machine open shop scheduling problem. The objective is to minimize the makespan. Jobs arrive over time. We study preemption-resume model, i.e., the currently processed job may be preempted at any moment in necessary and be resumed some time later. Let p _{1, j} and p _{2, j} denote the processing time of a job J _j on the two machines M ₁ and M ₂, respectively. Bounded processing times mean that 1 ≤ p _{i, j}  ≤ α (i = 1, 2) for each job J _j , where α ≥ 1 is a constant number. We propose an optimal online algorithm with a competitive ratio ${\frac{5\alpha-1}{4\alpha}}$ .     

Solution of the NP-hard total tardiness minimization problem in scheduling theory

The classical NP-hard (in the ordinary sense) problem of scheduling jobs in order to minimize the total tardiness for a single machine 1‖ΣT _j is considered. An NP-hard instance of the problem is completely analyzed. A procedure for partitioning the initial set of jobs into subsets is proposed. Algorithms are constructed for finding an optimal schedule depending on the number of subsets. The complexity of the algorithms is O(n ²Σp _j ), where n is the number of jobs and p _j is the processing time of the jth job (j = 1, 2, …, n).     

Criteria for the strong regularity of J-inner functions and γ-generating matrices

The class of left and right strongly regular J-inner mvf's plays an important role in bitangential interpolation problems and in bitangential direct and inverse problems for canonical systems of integral and differential equations. A new criterion for membership in this class is presented in terms of the matricial Muckenhoupt condition (A₂) that was introduced for other purposes by Treil and Volberg. Analogous results are also obtained for the class of γ-generating functions that intervene in the Nehari problem. The new criterion is simpler than the criterion that we presented earlier. A determinental criterion is also presented.     

On determining the 4-rank of the ideal class group of a quadratic field

Let e_j denote the number of 2^j-invariants of the narrow ideal class group of a quadratic field $\text{Q}$(D^1/2). Pumplün has stated a criterion for e₂ > 0. The equivalence of this criterion to one arising from the Redei-Reichardt theorem is shown to be a graph-theoretic result, for which a direct proof is given.     

E_m函数类中Nevanlinna-Pick插值与广义Stieltjes矩量问题

令E\-m=(-∞,∞)＼∪[DD(]m[]j=1[DD)](α\-j,β\-j).函数类[WTHT]N[WTBX](E\-m)表示在上半复平面解析且虚部非负,在诸(α\-j,β\-j)(j=1,…,m)内解析且为实值的函数全体.该文用Hankel 向量方法建立[WTHT]N[WTBX](E\-m)函数类 中含有限(或无限可数)插值点的Nevanlinna Pick 问题与集合E\-m上 相关的非标准截断(或全)广义Stieltjes 矩量问题解集之间的一一对应.用类似于Riesz的办法建立E\-m上非标准截断广义Stieltjes矩量问题的可解性准则,从而获得了[WTHT]N[WTBX](E\-m)函数类中Nevanlinna Pick问题的可解性准则.     

Analysis of a time-dependent scheduling problem by signatures of deterioration rate sequences

In the paper a single machine time-dependent scheduling problem is considered. The processing time p_j of each job is described by a function of the starting time t of the job, p_j=1+α_jt, where the job deterioration rate α_j?0 for j=0,1,…,n and t?0. Jobs are nonpreemptable and independent, there are no ready times and no deadlines. The criterion of optimality of a schedule is the total completion time.First, the notion of a signature for a given sequence of job deterioration rates is introduced, two types of the signature are defined and their properties are shown. Next, on the basis of these properties a greedy polynomial-time approximation algorithm for the problem is formulated. This algorithm, starting from an initial sequence, iteratively constructs a new sequence concatenating the previous sequence with new elements, according to the sign of one of the signatures of this sequence.Finally, these results are applied to the problem with job deterioration rates which are consecutive natural numbers, α_j=j for j=0,1,…,n. Arguments supporting the conjecture that in this case the greedy algorithm is optimal are presented.     

A transformation from Hausdorff to Stieltjes moment sequences

We introduce a non-linear injective transformation τ from the set of non-vanishing normalized Hausdorff moment sequences to the set of normalized Stieltjes moment sequences by the formulaT[(a _n ) _n=1 ^∞ ] _n = 1/a₁ ...a _n . Special cases of this transformation have appeared in various papers on exponential functionals of Lévy processes, partly motivated by mathematical finance. We give several examples of moment sequences arising from the transformation and provide the corresponding measures, some of which are related toq-series.     

The complexity of generalized clique packing

The K_i - j packing problem P_{i, j} is defined as follows: Given a graph G and integer k does there exist a set of at least kK_i's in G such that no two of these K_i's intersect in more than j nodes. This problem includes such problems as matching, vertex partitioning into complete subgraphs and edge partitioning into complete subgraphs. In this paper it is shown thhat for i ? 3 and 0?j?i ?2 the P_{i, j} problems is NP-complete. Furthermore, the problems remains NP-complete for i?3 and 1?j?i ?2 for chordal graphs.     

On an operator approach to interpolation problems for Stieltjes functions

A general interpolation problem for operator-valued Stieltjes functions is studied using V. P. Potapov's method of fundamental matrix inequalities and the method of operator identities. The solvability criterion is established and under certain restrictions the set of all solutions is parametrized in terms of a linear fractional transformation. As applications of a general theory, a number of classical and new interpolation problems are considered.