Selection in Monotone Matrices and Computingkth Nearest Neighbors

Anm×nmatrix =(a_{i, j}), 1≤i≤mand 1≤j≤n, is called atotally monotonematrix if for alli₁, i₂, j₁, j₂, satisfying 1≤i₁<i₂≤m, 1≤j₁<j₂≤n.[formula]We present an[formula]time algorithm to select thekth smallest item from anm×ntotally monotone matrix for anyk≤mn. This is the first subquadratic algorithm for selecting an item from a totally monotone matrix. Our method also yields an algorithm of the same time complexity for ageneralized row-selection problemin monotone matrices. Given a setS={p₁,…, p_n} ofnpoints in convex position and a vectork={k₁,…, k_n}, we also present anO(n^4/3log^c n) algorithm to compute thek_ith nearest neighbor ofp_ifor everyi≤n; herecis an appropriate constant. This algorithm is considerably faster than the one based on a row-selection algorithm for monotone matrices. If the points ofSare arbitrary, then thek_ith nearest neighbor ofp_i, for alli≤n, can be computed in timeO(n^7/5 log^c n), which also improves upon the previously best-known result.     

Complexity results for scheduling tasks with discrete starting times

Suppose that n independent tasks are to be scheduled without preemption on a set of identical parallel processors. Each task T_i requires a given execution time τ_i and it may be started for execution on any processor at any of its prescribed starting times s_i1, s_i2, …, s_iki, with k_i ≤ k for some fixed integer k. We first prove that the problem of finding a feasible schedule on a single processor is NP-complete in the strong sense even when τ_i ε {τ, τ′} and k_i ≤ 3 for 1 ≤ i ≤ n. The same problem is, however, shown to be solvable in O(n log n) time, provided s_iki − s_i1 < τ_i for 1 ≤ i ≤ n. We then show that the problem of finding a feasible schedule on an arbitrary number of processors is strongly NP-complete even when τ_i ε {τ, τ′}, k_i = 2 and s_i2 − s_i1 = δ < τ_i for 1 ≤ i ≤ n. Finally a special case with k_i = 2 and s_i2 − s_i1 = 1, 1 ≤ i ≤ n, of the above multiprocessor scheduling problem is shown to be solvable in polynomial time.     

Permanence and global stability in a Lotka-Volterra predator-prey system with delays

Consider the permanence and global asymptotic stability of models governed by the following Lotka-Volterra-type system:

, with initial conditions

x_i(t) = φ_i(t) ≥ o, t ≤ t₀, and φ_i(t₀) > 0. 1 ≤ i ≤n

. We define x₀(t) = x_n+1(t)≡0 and suppose that φ_i(t), 1 ≤ i ≤ n, are bounded continuous functions on [t₀, + ∞) and γ_i, α_i, c_i > 0,γ_i,j ≥ 0, for all relevant i,j.Extending a technique of Saito, Hara and Ma[1] for n = 2 to the above system for n ≥ 2, we offer sufficient conditions for permanence and global asymptotic stability of the solutions which improve the well-known result of Gopalsamy.     

Comonotone Jackson's Inequality

Let 2s points y_i=−πy_2s<…<y₁<π be given. Using these points, we define the points y_i for all integer indices i by the equality y_i=y_i+2s+2π. We shall write fΔ⁽¹⁾(Y) if f is a 2π-periodic continuous function and f does not decrease on [y_i, y_i−1], if i is odd; and f does not increase on [y_i, y_i−1], if i is even. In this article the following Theorem 1—the comonotone analogue of Jackson's inequality—is proved. 1. If fΔ⁽¹⁾(Y), then for each nonnegative integer n there is a trigonometric polynomial τ_n(x) of order n such that τ_nΔ⁽¹⁾(Y), and |f(x)−π_n(x)|c(s) ω(f; 1/(n+1)), x , where ω(f; t) is the modulus of continuity of f, c(s)=const. Depending only on s.     

Best Approximation with Linear Constraints: A Model Example

We consider best approximation in L_p( ), 1 ≤ p ≤ ∞, by means of entire functions y of exponential type subject to additional constraints Γ_j(y) = 0, j = 1, ..., K. Here Γ_j are (unbounded) linear functionals of the form Γ_j(y) = Dⁿy(s_j) − ∑ a_kD^ky(s_j) where s_j are fixed points.     

Algebraic Approaches to Periodic Arithmetical Maps

A residue class a + n with weight λ is denoted by λ, a, n. For a finite system = {λ_s, a_s, n_s}^k_{s = 1} of such triples, the periodic map w (x) = ∑_{ns|x − as} λ_s is called the covering map of . Some interesting identities for those with a fixed covering map have been known; in this paper we mainly determine all those functions f : Ω → such that ∑^k_{s = 1} λ_sf(a_s + n_s ) depends only on w where Ω denotes the family of all residue classes. We also study algebraic structures related to such maps f, and periods of arithmetical functions ψ(x) = ∑^k_{s = 1} λ_se^2πia_sx/n_s and ω(x) = |{1 ≤ s ≤ k : (x + a_s, n_s) = 1}|.     

Prophet regions and sharp inequalities for pth absolute moments of martingales

Exact comparisons are made relating E|Y₀|^p, E|Y_n−1|^p, and E(max_j≤n−1 |Y_j|^p), valid for all martingales Y₀,…,Y_n−1, for each p ≥ 1. Specifically, for p > 1, the set of ordered triples {(x, y, z) : X = E|Y₀|^p, Y = E |Y_n−1|^p, and Z = E(max_j≤n−1 |Y_j|^p) for some martingale Y₀,…,Y_n−1} is precisely the set {(x, y, z) : 0≤x≤y≤z≤Ψ_n,p(x, y)}, where Ψ_n,p(x, y) = xψ_n,p(y/x) if x > 0, and = a_n−1,py if x = 0; here ψ_n,p is a specific recursively defined function. The result yields families of sharp inequalities, such as E(max_j≤n−1 |Y_j|^p) + ψ_n,p^*(a) E |Y₀|^p ≤ aE |Y_n−1|^p, valid for all martingales Y₀,…,Y_n−1, where ψ_n,p^* is the concave conjugate function of ψ_n,p. Both the finite sequence and infinite sequence cases are developed. Proofs utilize moment theory, induction, conjugate function theory, and functional equation analysis.     

Shape-Preserving Smoothing of 3-Convex Splines of Degree 4

For every 3-convex piecewise-polynomial function s of degree ≤4 with n equidistant knots on [0, 1] we construct a 3-convex spline s ₁ (s ₁ ∈ C ⁽³⁾) of degree ≤4 with the same knots that satisfies the inequality

On a Conjecture Concerning Strong Unicity Constants

Let fC[−1, 1] be real-valued. We consider the sequence of strong unicity constants (γ_n(f))_n induced by the polynomials of best uniform approximation of f. It is proved that lim inf_n→∞ γ_n(f)=0, whenever f is not a polynomial.     

On the Convergence and Iterates of q-Bernstein Polynomials

The convergence properties of q-Bernstein polynomials are investigated. When q1 is fixed the generalized Bernstein polynomials _nf of f, a one parameter family of Bernstein polynomials, converge to f as n→∞ if f is a polynomial. It is proved that, if the parameter 0<q<1 is fixed, then _nf→f if and only if f is linear. The iterates of _nf are also considered. It is shown that _n^Mf converges to the linear interpolating polynomial for f at the endpoints of [0,1], for any fixed q>0, as the number of iterates M→∞. Moreover, the iterates of the Boolean sum of _nf converge to the interpolating polynomial for f at n+1 geometrically spaced nodes on [0,1].     

On Score Sequences ofk-Hypertournaments

Given two nonnegative integers n and k withn ≥ k > 1, a k -hypertournament on n vertices is a pair (V, A), where V is a set of vertices with | V | = n and A is a set of k -tuples of vertices, called arcs, such that for any k -subset S ofV , A contains exactly one of the k!k -tuples whose entries belong to S. We show that a nondecreasing sequence (r₁, r₂, , r_n) of nonnegative integers is a losing score sequence of a k -hypertournament if and only if for each j(1 ≤ j ≤ n),with equality holding whenj = n. We also show that a nondecreasing sequence (s₁,s₂ , , s_n) of nonnegative integers is a score sequence of somek -hypertournament if and only if for each j(1 ≤ j ≤ n),with equality holding whenj = n. Furthermore, we obtain a necessary and sufficient condition for a score sequence of a strong k -hypertournament. The above results generalize the corresponding theorems on tournaments.     

Omega result for the mean square of the Riemann zeta function

A recent method of Soundararajan enables one to obtain improved Ω-result for finite series of the form ∑_nf(n) cos (2πλ_nx+β) where 0≤λ₁≤λ₂≤. . . and β are real numbers and the coefficients f(n) are all non-negative. In this paper, Soundararajan’s method is adapted to obtain improved Ω-result for E(t), the remainder term in the mean-square formula for the Riemann zeta-function on the critical line. The Atkinson series for E(t) is of the above type, but with an oscillating factor (−1)ⁿ attached to each of its terms.     

On the L convergence of Lagrange interpolating entire functions of exponential type

Let f: be a continuous, 2π-periodic function and for each n ε let t_n(f; ·) denote the trigonometric polynomial of degree n interpolating f in the points 2kπ/(2n + 1) (k = 0, ±1, …, ±n). It was shown by J. Marcinkiewicz that lim_{n → ∞} ∝₀^2π¦f(θ) − t_n(f θ)¦^p dθ = 0 for every p > 0. We consider Lagrange interpolation of non-periodic functions by entire functions of exponential type τ > 0 in the points kπ/τ (k = 0, ± 1, ± 2, …) and obtain a result analogous to that of Marcinkiewicz.     

Uniform estimates for polynomial approximation in domains with corners

Let be a domain with a Jordan boundary ∂G, consisting of l smooth curves Γ_j, such that {z_j}Γ_j-1∩Γ_j≠, j=1,…,l, where Γ₀Γ_l. Denote by α_jπ, 0<α_j2, the angles at z_j's between the curves Γ_j-1 and Γ_j, exterior with respect to G. Let Φ be a conformal mapping of the exterior of onto the exterior of the unit disk, normed by Φ^′(∞)>0. We assume that there is a neighborhood U of , such that , where

z≠z_j if α_j1. Set g_Gsup{|g(z)|:zG}. Then we prove Theorem. Let and 0βr. If a function f is analytic in G and f^(r)β_G<+∞, then for each nlr there is an algebraic polynomial P_n of degree <n, such that

     

Prophet inequalities for parallel processes

Generalizations of prophet inequalities for single sequences are obtained for optimal stopping of several parallel sequences of independent random variables. For example, if {X_{i, j}, 1 ≤ i ≤ n, 1 ≤ j < ∞} are independent non-negative random variables, then

Full-size image

and this bound is best possible. Applications are made to comparisons of the optimal expected returns of various alternative methods of stopping of parallel processes.     

Lambda-determinants and domino-tilings

Consider the 2n-by-2n matrix with m_i,j=1 for i,j satisfying |2i−2n−1|+|2j−2n−1|2n and m_i,j=0 for all other i,j, consisting of a central diamond of 1's surrounded by 0's. When n4, the λ-determinant of the matrix M (as introduced by Robbins and Rumsey [Adv. Math. 62 (1986) 169–184]) is not well defined. However, if we replace the 0's by t's, we get a matrix whose λ-determinant is well defined and is a polynomial in λ and t. The limit of this polynomial as t→0 is a polynomial in λ whose value at λ=1 is the number of domino-tilings of a 2n-by-2n square.     

Prophet inequalities for cost of observation stopping problems

Comparisons are made between the expected gain of a prophet (an observer with complete foresight) and the maximal expected gain of a gambler (using only non-anticipating stopping times) observing a sequence of independent, uniformly bounded random variables where a non-negative fixed cost is charged for each observation. Sharp universal bounds are obtained under various restrictions on the cost and the length of the sequence. For example, it is shown for X₁, X₂, … independent, [0, 1]-valued random variables that for all c ≥ 0 and all n ≥ 1 that E(max_{1 ≤ j ≤ n}(X_j − jc)) − sup_{t Tn} E(X_t − tc) ≤ 1/e, where T_n is the collection of all stopping times t which are less than or equal to n almost surely.     

Quadrature formulae connected to σ-orthogonal polynomials

Let dλ(t) be a given nonnegative measure on the real line , with compact or infinite support, for which all moments exist and are finite, and μ₀>0. Quadrature formulas of Chakalov–Popoviciu type with multiple nodes

where σ=σ_n=(s₁,s₂,…,s_n) is a given sequence of nonnegative integers, are considered. A such quadrature formula has maximum degree of exactness d_max=2∑_ν=1ⁿs_ν+2n−1 if and only if

The proof of the uniqueness of the extremal nodes τ₁,τ₂,…,τ_n was given first by Ghizzetti and Ossicini (Rend. Mat. 6(8) (1975) 1–15). Here, an alternative simple proof of the existence and the uniqueness of such quadrature formulas is presented. In a study of the error term R(f), an influence function is introduced, its relevant properties are investigated, and in certain classes of functions the error estimate is given. A numerically stable iterative procedure, with quadratic convergence, for determining the nodes τ_ν, ν=1,2,…,n, which are the zeros of the corresponding σ-orthogonal polynomial, is presented. Finally, in order to show a numerical efficiency of the proposed procedure, a few numerical examples are included.     

Sequences with equi-distributed extreme points in uniform polynomial approximation

Let E be a compact set in with connected complement and positive logarithmic capacity. For any f continuous on E and analytic in the interior of E, we consider the distribution of extreme points of the error of best uniform polynomial approximation on E. Let Λ=(n_j) be a subsequence of such that n_j+1/n_j→1. If, for nΛ, A_n( f)∂E denotes the set of extreme points of the error function, we prove that there is a subsequence Λ′ of Λ such that the distribution of any (n+2)th Fekete point set of A_n( f) tends weakly to the equilibrium distribution on E as n→∞ in Λ′. Furthermore, we prove a discrepancy result for the distribution of the point sets if the boundary of E is smooth enough.     

Convexity preserving and predicting by Bernstein polynomials

It is known that the Bernstein polynomials of a function f defined on [0, 1 ] preserve its convexity properties, i.e., if f⁽ⁿ⁾ 0 then for m n, (B_mf)⁽ⁿ⁾ 0. Moreover, if f is n-convex then (B_mf)⁽ⁿ⁾ 0. While the converse is not true, we show that if f is bounded on (a, b) and if for every subinterval [α, β] (a, b) the nth derivative of the mth Bernstein polynomial of f on [α, β] is nonnegative then f is n-convex.