Minimizing a monotone concave function with laminar covering constraints

Let V be a finite set with |V|=n. A family F⊆2^V is called laminar if for all two sets X,Y∈F, X∩Y≠∅ implies X⊆Y or X⊇Y. Given a laminar family F, a demand function , and a monotone concave cost function , we consider the problem of finding a minimum-cost such that x(X)?d(X) for all X∈F. Here we do not assume that the cost function F is differentiable or even continuous. We show that the problem can be solved in O(n²q) time if F can be decomposed into monotone concave functions by the partition of V that is induced by the laminar family F, where q is the time required for the computation of F(x) for any . We also prove that if F is given by an oracle, then it takes Ω(n²q) time to solve the problem, which implies that our O(n²q) time algorithm is optimal in this case. Furthermore, we propose an algorithm if F is the sum of linear cost functions with fixed setup costs. These also make improvements in complexity results for source location and edge-connectivity augmentation problems in undirected networks. Finally, we show that in general our problem requires Ω(2^n/2q) time when F is given implicitly by an oracle, and that it is NP-hard if F is given explicitly in a functional form.     

Large deviations for martingales and derivatives

Fix a sequence of positive integers (mn) and a sequence of positive real numbers (wn). Two closely related sequences of linear operators (Tn) are considered. One sequence has given by the Lebesgue derivatives . The other sequence has given by the dyadic martingale when (l−1)/n²?x<l/n² for l=1,…,n². We prove both positive and negative results concerning the convergence of .     

The Cameron-Erd?s conjecture

A subset A of integers is said to be sum-free if a+b∉A for any a,b∈A. Let s(n) be the number of sum-free sets in interval [1,n] of integers. P. Cameron and P. Erd?s conjectured that s(n)=O(2^n/2). We show that for even n and for odd n, where are absolute constants, thereby proving the conjecture.     

Computing an eigenvector of an inverse Monge matrix in max-plus algebra

The problem of computing an eigenvector of an inverse Monge matrix in max-plus algebra is addressed. For a general matrix, the problem can be solved in at most O(n³) time. This note presents an O(n²) algorithm for computing one max-plus algebraic eigenvector of an inverse Monge matrix . It is assumed that is irreducible.     

Coloring the complements of intersection graphs of geometric figures

Let be the complement of the intersection graph G of a family of translations of a compact convex figure in Rⁿ. When n=2, we show that , where γ(G) is the size of the minimum dominating set of G. The bound on is sharp. For higher dimension we show that , for n?3. We also study the chromatic number of the complement of the intersection graph of homothetic copies of a fixed convex body in Rⁿ.     

The Dirichlet Markov Ensemble

We equip the polytope of n×n Markov matrices with the normalized trace of the Lebesgue measure of Rⁿ². This probability space provides random Markov matrices, with i.i.d. rows following the Dirichlet distribution of mean (1/n,…,1/n). We show that if is such a random matrix, then the empirical distribution built from the singular values of tends as n→∞ to a Wigner quarter-circle distribution. Some computer simulations reveal striking asymptotic spectral properties of such random matrices, still waiting for a rigorous mathematical analysis. In particular, we believe that with probability one, the empirical distribution of the complex spectrum of tends as n→∞ to the uniform distribution on the unit disc of the complex plane, and that moreover, the spectral gap of is of order when n is large.     

An application of anisotropic regularization to the existence of weak Pareto minimal points

Given a function f on Rⁿ, we introduce the concept of anisotropic regularization as a generalization of Tikhonov regularization f_ε(x)=f(x)+εx. When f is a continuous -function on Rⁿ and K is a box in Rⁿ, we study the properties of and the limiting behavior of solutions of a regularized box variational inequality problem , with emphasis on the existence of weak Pareto minimal points with respect to K. This work generalizes results of Sznajder and Gowda (1998) proved in the setting of nonlinear complementarity problems.     

Bound states and the Szeg? condition for Jacobi matrices and Schrödinger operators

For Jacobi matrices with a_n=1+(−1)ⁿαn^−γ, b_n=(−1)ⁿβn^−γ, we study bound states and the Szeg? condition. We provide a new proof of Nevai's result that if , the Szeg? condition holds, which works also if one replaces (−1)ⁿ by . We show that if α=0, β≠0, and , the Szeg? condition fails. We also show that if γ=1, α and β are small enough ( will do), then the Jacobi matrix has finitely many bound states (for α=0, β large, it has infinitely many).     

Quartic, octic residues and Lucas sequences

Let be a prime and a,b∈Z with a²+b²≠p. Suppose p=x²+(a²+b²)y² for some integers x and y. In the paper we develop the calculation technique of quartic Jacobi symbols and use it to determine . As applications we obtain the congruences for modulo p and the criteria for (if ), where {Un} is the Lucas sequence given by U₀=0, U₁=1 and Un+1=bUn+k²Un−1(n?1). We also pose many conjectures concerning , or .     

Toeplitz operators associated to commuting row contractions

Let H be a complex Hilbert space and let {Tn}_n?1 be a sequence of commuting bounded operators on H such that . Let denote the space of all operators X in B(H) for which and suppose that . We will show that there exists a triple {K,Γ,{Un}_n?1} where K is a Hilbert space, Γ:K→H is a bounded operator and {Un}_n?1⊂B(K) is a sequence of commuting normal operators with such that TnΓ=ΓUn for n?1, and for which the mapping Y?ΓYΓ^∗ is a complete isometry from the commutant of {Un}_n?1 onto the space . Moreover we show that the inverse of this mapping can be extended to a ^∗-homomorphism

     

On the variety parameterizing completely decomposable polynomials

The purpose of this paper is to relate the variety parameterizing completely decomposable homogeneous polynomials of degree d in n+1 variables on an algebraically closed field, called , with the Grassmannian of (n−1)-dimensional projective subspaces of P^n+d−1. We compute the dimension of some secant varieties to . Moreover by using an invariant embedding of the Veronese variety into the Plücker space, we are able to compute the intersection of G(n−1,n+d−1) with , some of its secant varieties, the tangential variety and the second osculating space to the Veronese variety.     

Efficient computation of 2-medians in a tree network with positive/negative weights

We consider a variant of the classical two median facility location problem on a tree in which vertices are allowed to have positive or negative weights. This problem was proposed by Burkard et al. in 2000 (R.E. Burkard, E. Çela, H. Dollani, 2-medians in trees with pos/neg-weights, Discrete Appl. Math. 105 (2000) 51-71). who looked at two objectives, finding the total minimum weighted distance (MWD) and the total weighted minimum distance (WMD). Their approach finds an optimal solution in O(n²) time and O(n³) time, respectively, with better performance for special trees such as paths and stars. We propose here an O(nlogn) algorithm for the MWD problem on trees of arbitrary shape. We also briefly discuss the WMD case and argue that it can be solved in time. However, a systematic exposition of the later case cannot be contained in this paper.     

On T-sequences and characterized subgroups

Let X be a compact metrizable abelian group and u={un} be a sequence in its dual group X^∧. Set su(X)={x:(un,x)→1} and . Let G be a subgroup of X. We prove that G=su(X) for some u iff it can be represented as some dually closed subgroup Gu of . In particular, su(X) is polishable. Let u={un} be a T-sequence. Denote by the group X^∧ equipped with the finest group topology in which un→0. It is proved that and . We also prove that the group generated by a Kronecker set cannot be characterized.     

On an inhomogeneous slip-inflow boundary value problem for a steady flow of a viscous compressible fluid in a cylindrical domain

We investigate a steady flow of a viscous compressible fluid with inflow boundary condition on the density and inhomogeneous slip boundary conditions on the velocity in a cylindrical domain Ω=Ω₀×(0,L)∈R³. We show existence of a solution , p>3, where v is the velocity of the fluid and ρ is the density, that is a small perturbation of a constant flow (, ). We also show that this solution is unique in a class of small perturbations of . The term u⋅∇w in the continuity equation makes it impossible to show the existence applying directly a fixed point method. Thus in order to show existence of the solution we construct a sequence (vn,ρn) that is bounded in and satisfies the Cauchy condition in a larger space L_∞(0,L;L₂(Ω₀)) what enables us to deduce that the weak limit of a subsequence of (vn,ρn) is in fact a strong solution to our problem.     

Self-duality of bounded monotone boolean functions and related problems

In this paper we examine the problem of determining the self-duality of a monotone boolean function in disjunctive normal form (DNF). We show that the self-duality of monotone boolean functions with n disjuncts such that each disjunct has at most k literals can be determined in O(2^k2k²n) time. This implies an O(n²logn) algorithm for determining the self-duality of -DNF functions. We also consider the version where any two disjuncts have at most c literals in common. For this case we give an O(n^4(c+1)) algorithm for determining self-duality.