Inequalities for Cyclic Functions

The nth cyclic function is defined by

Full-size image

We prove that if k is an integer with 1kn−1, then

Full-size image

holds for all positive real numbers x with the best possible constantsα=1 and β= 2n-k over n.     

Precise asymptotics in some strong limit theorems for multidimensionally indexed random variables

Consider Z₊^d (d2)—the positive d-dimensional lattice points with partial ordering , let {X_k,kZ₊^d} be i.i.d. random variables with mean 0, and set S_n=∑_knX_k, nZ₊^d. We establish precise asymptotics for ∑_n|n|^r/p−2P(|S_n||n|^1/p), and for

Full-size image

, (0δ1) as 0, and for

Full-size image

as .     

Boundedness by 3 of the Whitney Interpolation Constant

Let the function fC[0,1] satisfy f( . We prove the estimate

Full-size image

.     

z-Approximations

Approximation algorithms for NP-hard optimization problems have been widely studied for over three decades. Most of these measure the quality of the solution produced by taking the ratio of the cost of the solution produced by the algorithm to the cost of an optimal solution. In certain cases, this ratio may not be very meaningful—for example, if the ratio of the worst solution to the best solution is at most some constant α, then an approximation algorithm with factor α may in fact yield the worst solution! To overcome this hurdle (among others), several authors have independently suggested the use of a different measure which we call z-approximation. An algorithm is an α z-approximation if it runs in polynomial time and produces a solution whose distance from the optimal one is at most α times the distance between the optimal solution and the worst possible solution. The results known so far about z-approximations are either of the inapproximability type or rather straightforward observations. We design polynomial time algorithms for several fundamental discrete optimization problems; in particular we obtain a z-approximation factor of for the

Full-size image

(TSP) (with no triangle inequality assumption). For the TSP this improves to . We also show that if there is a polynomial time algorithm that for any fixed ε > 0 yields an ε z-approximation then P = NP. We also present z-approximations for severa1 other problems such as

Full-size image

, and

Full-size image

.     

Orthogonal Rational Functions and Nested Disks

In Akhiezer's book [“The Classical Moment Problem and Some Related Questions in Analysis,” Oliver & Boyd, Edinburghasol;London, 1965] the uniqueness of the solution of the Hamburger moment problem, if a solution exists, is related to a theory of nested disks in the complex plane. The purpose of the present paper is to develop a similar nested disk theory for a moment problem that arises in the study of certain orthogonal rational functions. Let {α_n}^∞_n=0be a sequence in the open unit disk in the complex plane, let

Full-size image

( /|α_k|=−1 whenα_k=0), and let

Full-size image

We consider the following “moment” problem: Given a positive-definite Hermitian inner product ·, · on × , find a non-decreasing functionμon [−π, π] (or a positive Borel measureμon [−π,π)) such that

Full-size image

In particular we give necessary and sufficient conditions for the uniqueness of the solution in the case that If this series diverges the solution is always unique.     

Oblique Projections and Abstract Splines

Given a closed subspace of a Hilbert space and a bounded linear operator AL( ) which is positive, consider the set of all A-self-adjoint projections onto :

Full-size image

In addition, if ₁ is another Hilbert space, T: → ₁ is a bounded linear operator such that T^*T=A and ξ , consider the set of (T, ) spline interpolants to ξ:

Full-size image

A strong relationship exists between (A, ) and sp(T, ,ξ). In fact, (A, ) is not empty if and only if s p(T, ,ξ) is not empty for every ξ . In this case, for any ξ it holds

Full-size image

and for any ξ , the unique vector of s p(T, ,ξ) with minimal norm is (1−P_A, )ξ, where P_A, is a distinguished element of (A, ). These results offer a generalization to arbitrary operators of several theorems by de Boor, Atteia, Sard and others, which hold for closed range operators.     

An Improvement of the Constants in a Reverse Integral Inequality

We present an upper bound for the ratio [formula], where f is a positive decreasing function satisfying

Full-size image

for all t (0, a]. Our result sharpens an inequality of L. Nania.     

Weierstrass'' Theorem in Weighted Sobolev Spaces

We characterize the set of functions which can be approximated by polynomials with the following norm

Full-size image

for a big class of weights w₀, w₁, …, w_k     

Inequalities for Rational Functions

A new hyperbolic area estimate for the level sets of finite Blaschke products is presented. The following inversion of the usual Sobolev embedding theorem is proved:

Full-size image

Hereris a rational function of degreenwith poles outside . This estimate implies a new inverse theorem for rational approximation of analytic functions with respect to areaL^pnorm.     

Periodic solutions of a nonlinear second order differential equation with delay

It is proved that the autonomous difference-differential equation

Full-size image

(0) has, for a broad class of functions f, a nonconstant periodic solution whenever the associated characteristic equation has a root with positive real part.     

The Bernstein Constant and Polynomial Interpolation at the Chebyshev Nodes

In this paper, we establish new asymptotic relations for the errors of approximation in L_p[−1,1], 0<p∞, of x^λ, λ>0, by the Lagrange interpolation polynomials at the Chebyshev nodes of the first and second kind. As a corollary, we show that the Bernstein constant

Full-size image

is finite for λ>0 and .     

Restricted T-Universal Functions

We prove the existence of a function which is holomorphic exactly in the unit disk and has universal translates with respect to a prescribed closed set E∂ and satisfies C^∞(∂ \E). If Q is a subsequence of ₀ with upper density d(Q)=1 then the function can be constructed such that in addition

Full-size image

     

Minimal Extensions in Tensor Product Spaces

LetX,Ybe two separable Banach spaces and letVXandWYbe finite dimensional subspaces. Suppose thatVSX,WZYand letM (S, V),N (Z, W). We will prove that ifαis a reasonable, uniform crossnorm onXYthenλ_MN(V_αW,X_αY)=λ_M(V, X) λ_N(W, Y).Here for any Banach spaceX,VSXandM (S, V)

Full-size image

Also some applications of the above mentioned result will be presented.     

Best Approximation and Cyclic Variation Diminishing Kernels

We study best uniform approximation of periodic functions from

Full-size image

where the kernelK(x, y) is strictly cyclic variation diminishing, and related problems including periodic generalized perfect splines. For various approximation problems of this type, we show the uniqueness of the best approximation and characterize the best approximation by extremal properties of the error function. The results are proved by using a characterization of best approximants from quasi-Chebyshev spaces and certain perturbation results.     

Functions of class Lip(α, p) and their Taylor mean

The object of this paper is to study the rapidity of convergence of the Taylor mean of the Fourier series of ƒ(x) when ƒ(x) belongs to the class Lip(α, p). We show that it is of Jackson order provided that a suitable integrability condition is imposed upon the function

Full-size image

.     

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.     

The limit of the product of the parameterized exponentials of two operators

Given two self-adjoint, positive, compact operators A,B on a separable Hilbert space, we show that there exists a self-adjoint, positive, compact operator C commuting with B such that

Full-size image

.     

A Chebyshev Set and its Distance Function

We prove that in a Banach space X with rotund dual X^* a Chebyshev set C is convex iff the distance function d_C is regular on X\C iff d_C admits the strict and Gâteaux derivatives on X\C which are determined by the subdifferential ∂x−

Full-size image

x" height="11" width="10"> for each xX\C and

Full-size image

x" height="11" width="10">P_C(x)\{cC:x−c=d_C(x)}. If X is a reflexive Banach space with smooth and Kadec norm then C is convex iff it is weakly closed iff P_C is continuous. If the norms of X and X^* are Fréchet differentiable then C is convex iff d_C is Fréchet differentiable on X\C. If also X has a uniformly Gâteaux differentiable norm then C is convex iff the Gâteaux (Fréchet) subdifferential ∂⁻d_C(x) (∂_Fd_C(x)) is nonempty on X\C.     

Partially dynamic maintenance of minimum weight hyperpaths

We address the problem of dynamically maintaining minimum weight hyperpaths in a directed hypergraph in a decremental setting. For such a problem, we provide a new efficient algorithm that works for a wide class of hyperpath weight measures. This algorithm explicitly updates minimum weight hyperpaths in

Full-size image

worst case time under a sequence of L hyperarc weight increments and hyperarc deletions, where C is the maximum weight of minimum hyperpaths in and is the size of the representation of the hypergraph. Hyperpath weight measures are only required to belong to the class of strict weakly superior functions.     

A high-order method for the approximate identification of the matrix of a linear differential system

For a linear differential system y′ = Ay with unknown matrix A, we approximate A by a particular linear combination of values of the observed exponential matrix

Full-size image

and show that the L₁ norm of the error matrix is O(hⁿ).