Duality for max-separable problems

In this paper we propose a general duality theory for a class of so called ‘max-separable’ optimization problems. In such problems functions h:R ^k → R of the form h(x ₁, . . . , x _k ) =? max _j ? h _j (x _j ), occur both as objective functions and as constraint functions (h _j are assumed to be strictly increasing functions of one variable). As a result we obtain pairs of max-separable optimization problems, which possess both weak and strong duality property without a duality gap.     

Heuristic procedures for the m-partial cover problem on a plane

The m-partial cover problem on a plane is defined as follows: given npoints located at cartesian coordinates (x_j, y_j) (j=1,…,n) each with an associated weight w_j, a critical distance R and an integer number m, determine the location of m centres so that the sum of the weights of those points lying within distance R of at least one centre is maximised. Five heuristic procedures to solve the m-partial cover problem are presented and computational experience reported. The use of the procedures for some related problems is discussed.     

Valuations, equimultiplicity and normal flatness

Let R be a regular noetherian local ring of dimension n≥2 and (R_i)≡R=R₀⊂R₁⊂R₂⊂?⊂R_i⊂? be a sequence of successive quadratic transforms along a regular prime ideal p of R (i.e if p_i is the strict transform of p in R_i, then p_i≠R_i, i≥0). We say that p is maximal for (R_i) if for every non-negative integer j≥0 and for every prime ideal q_j of R_j such that (R_i) is a quadratic sequence along q_j with p_j⊂q_j, we have p_j=q_j. We show that p is maximal for (R_i) if and only if V=∪_i≥0R_i/p_i is a valuation ring of dimension one. In this case, the equimultiple locus at p is the set of elements of the maximal ideal of R for which the multiplicity is stable along the sequence (R_i), provided that the series of real numbers given by the multiplicity sequence associated with V diverges. Furthermore, if we consider an ideal J of R, we also show that is normally flat along at the closed point if and only if the Hironaka’s character ν^∗(J,R) is stable along the sequence (R_i). This generalizes well known results for the case where p has height one (see [B.M. Bennett, On the characteristic functions of a local ring, Ann. of Math. Second Series 91 (1) (1970) 25-87]).     

Commuting self-adjoint partial differential operators and a group theoretic problem

In Rⁿ let Ω denote a Nikodym region (= a connected open set on which every distribution of finite Dirichlet integral is itself in $\text{L}{}^2\text{(Ω))}$. The existence of n commuting self-adjoint operators $\text{H}{}_1\text{,…, H}{}_{\mathrm{n}}\text{in}\text{L}{}^2\text{(Ω)}$ such that each H_j is a restriction of $\text{?i β}\text{βx}{}_{\mathrm{j}}$ (acting in the distribution sense) is shown to be equivalent to the existence of a set Λ ?Rⁿ such that the restrictions to Ω of the functions exp i ∑ λ_jx_j form a total orthogonal family in $\text{L}{}^2\text{(Ω)}$. If it is required, in addition, that the unitary groups generated by H₁,…, H_n act multiplicatively on $\text{L}{}^2\text{(Ω)}$, then this is shown to correspond to the requirement that Λ can be chosen as a subgroup of the additive group Rⁿ. The measurable sets Ω ?Rⁿ (of finite Lebesgue measure) for which there exists a subgroup Λ ?Rⁿ as stated are precisely those measurable sets which (after a correction by a null set) form a system of representatives for the quotient of Rⁿ by some subgroup Γ (essentially the dual of Λ).     

A counter example for nilpotent groups

Let R be a ring with 1, I be a nilpotent subring of R (there exists a natural number n, such that In = 0), and I be generated by {xj |j ∈ J} as ring. Write U = 1 + I, and it is a nilpotent group with class ≤ n - 1. Let G be the subgroup of U which is generated by {1 + xj|j ∈ J}. The group constructed in this paper indicates that the nilpotency class of G can be less than that of U.     

Extensions of band matrices with band inverses

Let R_ij be a given set of μ_i× μ_j matrices for i, j=1,…, n and |i?j| ?m, where 0?m?n?1. Necessary and sufficient conditions are established for the existence and uniqueness of an invertible block matrix =[F_ij], i,j=1,…, n, such that F_ij=R_ij for |i?j|?m, F admits either a left or right block triangular factorization, and (F^?1)_ij=0 for |i?j|>m. The well-known conditions for an invertible block matrix to admit a block triangular factorization emerge for the particular choice m=n?1. The special case in which the given R_ij are positive definite (in an appropriate sense) is explored in detail, and an inequality which corresponds to Burg's maximal entropy inequality in the theory of covariance extension is deduced. The block Toeplitz case is also studied.     

Inner and outerj-radii of convex bodies in finite-dimensional normed spaces

This paper is concerned with the various inner and outer radii of a convex bodyC in ad-dimensional normed space. The innerj-radiusr _j (C) is the radius of a largestj-ball contained inC, and the outerj-radiusR _j (C) measures how wellC can be approximated, in a minimax sense, by a (d —j)-flat. In particular,r _d (C) andR _d (C) are the usual inradius and circumradius ofC, while 2r ₁(C) and 2R ₁(C) areC's diameter and width.Motivation for the computation of polytope radii has arisen from problems in computer science and mathematical programming. The radii of polytopes are studied in [GK1] and [GK2] from the viewpoint of the theory of computational complexity. This present paper establishes the basic geometric and algebraic properties of radii that are needed in that study.Much of this paper was written when both authors were visiting the Institute for Mathematics and Its Applications, 206 Church Street S.E., Minneapolis, MN 55455, USA. The research of P. Gritzmann was supported in part by the Alexander-von-Humboldt Stiftung and the Deutsche Forschungsgemeinschaft. V. Klee's research was supported in part by the National Science Foundation.     

Boolean invertible matrices identified from two permutations and their corresponding Haar-type matrices

We construct a class R_m of m×m boolean invertible matrices whose elements satisfy the following property: when we perform the Hadamard product operation R_i⊙R_j on the set of row vectors {R₁,…,R_m} of an element R∈R_m we produce either the row R_max{i,j} or the zero row. In this paper, we prove that every matrix R∈R_m is uniquely determined by a pair of permutations of the set {1,…,m}. As a by-product of this result we identify Haar-type matrices from a pair of permutations as well, because these matrices emerge from the Gram-Schmidt orthonormalization process of the set of row vectors of R matrices belonging in a certain subclass R₀⊂R_m.     

Value distribution and shared sets of differences of meromorphic functions

We investigate value distribution and uniqueness problems of difference polynomials of meromorphic functions. In particular, we show that for a finite order transcendental meromorphic function f with λ(1/f)<ρ(f) and a non-zero complex constant c, if n?2, then fn(z)f(z+c) assumes every non-zero value a∈C infinitely often. This research also shows that there exist two sets S₁ with 9 (resp. 5) elements and S₂ with 1 element, such that for a finite order nonconstant meromorphic (resp. entire) function f and a non-zero complex constant c, Ef(z)(Sj)=Ef(z+c)(Sj)(j=1,2) imply f(z)≡f(z+c). This gives an answer to a question of Gross concerning a finite order meromorphic function f and its shift.     

Splines with maximal zero sets

Consider a spline s(x) of degree n with L knots of specified multiplicities R₁, …, R_L, which satisfies r sign consistent mixed boundary conditions in addition to s⁽ⁿ⁾(a) = 1. Such a spline has at most n + 1 ?r + ∑_{j = 1}^LR_j zeros in (a, b) which fulfill an interlacing condition with the knots if s(x) ? = 0 everywhere. Conversely, given a set of n ?r + ∑_{j = 1}^LR_j zeros then for any choice η₁ < ··· < η_L of the knot locations which fulfills the interlacing condition with the zeros, the unique spline s(x) possessing these knots and zeros and satisfying the boundary conditions is such that s⁽ⁿ⁾(x) vanishes nowhere and changes sign at η_j if and only if R_j is odd. Moreover there exists a choice of the knot locations, not necessarily unique, which makes $\text{¦s}{}^{\mathrm{(n)}}\text{(x)¦ ≡ 1}$. In particular, this establishes the existence of monosplines and perfect splines with knots of given multiplicities, satisfying the mixed boundary conditions and possessing a prescribed maximal zero set. An application is given to double-precision quadrature formulas with mixed boundary terms and a certain polynomial extremal problem connected with it.     

Univariate multiquadric approximation: Quasi-interpolation to scattered data

The univariate multiquadric function with centerx _j ∈R has the form {? _j (x)=[(x?x _j )²+c ²]^1/2, x∈R} wherec is a positive constant. We consider three approximations, namely, ? _A f, ?_? f, and ? _C f, to a function {f(x),x ₀≤x≤x _N } from the space that is spanned by the multiquadrics {? _j :j=0, 1, ...,N} and by linear polynomials, the centers {x _j :j=0, 1,...,N} being given distinct points of the interval [x ₀,x _N ]. The coefficients of ? _A f and ?_? f depend just on the function values {f(x _j ):j=0, 1,...,N}. while ? _A f, ? _C f also depends on the extreme derivativesf′(x ₀) andf′(x _N ). These approximations are defined by quasi-interpolation formulas that are shown to give good accuracy even if the distribution of the centers in [x ₀,x _N ] is very irregular. Whenf is smooth andc=O(h), whereh is the maximum distance between adjacent centers, we find that the error of each quasi-interpolant isO(h ²|logh|) away from the ends of the rangex ₀≤x≤x _N. Near the ends of the range, however, the accuracy of ? _A f and ?_? f is onlyO(h), because the polynomial terms of these approximations are zero and a constant, respectively. Thus, some of the known accuracy properties of quasiinterpolation when there is an infinite regular grid of centers {x _j =jh:j ∈F} given by Buhmann (1988), are preserved in the case of a finite rangex ₀≤x≤x _N , and there is no need for the centers {x _j :j=0, 1, ...,N} to be equally spaced.     

Characterization of the absence of a spectral gapfor a class of periodic Jacobi operators

Let q ∈ {2, 3} and let 0 = s₀ < s₁ < … < s_q = T be integers. For m, n ∈ Z, we put ¯m,n = {j ∈ Z| m? j ? n}. We set l_j = s_j − s_j−1 for j ∈ 1, q. Given (p₁,, p_q) ∈ R^q, let b: Z → R be a periodic function of period T such that b(·) = p_j on s_j−1 + 1, s_j for each j ∈ 1, q. We study the spectral gaps of the Jacobi operator (Ju)(n) = u(n + 1) + u(n − 1) + b(n)u(n) acting on l²(Z). By [λ_2j , λ_2j−1] we denote the jth band of the spectrum of J counted from above for j ∈ 1, T. Suppose that p_m ≠ p_n for m ≠ n. We prove that the statements (i) and (ii) below are equivalent for λ ∈ R and i ∈ 1, T − 1.     

Multiresolution expansion, approximation order and quasiasymptotic behavior of tempered distributions

Multiresolution analysis of tempered distributions is studied through multiresolution analysis on the corresponding test function spaces Sr(R), r∈N₀. For a function h, which is smooth enough and of appropriate decay, it is shown that the derivatives of its projections to the corresponding spaces Vj, j∈Z, in a regular multiresolution analysis of L²(R), denoted by hj, multiplied by a polynomial weight converge in sup norm, i.e., hj→h in Sr(R) as j→∞. Analogous result for tempered distributions is obtained by duality arguments. The analysis of the approximation order of the projection operator within the framework of the theory of shift-invariant spaces gives a further refinement of the results. The order of approximation is measured with respect to the corresponding space of test functions. As an application, we give Abelian and Tauberian type theorems concerning the quasiasymptotic behavior of a tempered distribution at infinity.     

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.     

Schrödinger operators with singular potentials

Recently B. Simon proved a remarkable theorem to the effect that the Schrödinger operatorT=?Δ+q(x) is essentially selfadjoint onC ₀ ^∞ (R ^m if 0≦q ∈L ²(R ^m). Here we extend the theorem to a more general case,T=?Σ _j ^=1/m (?/?x _j ?ib _j(x))² +q ₁(x) +q ₂(x), whereb _j, q₁,q ₂ are real-valued,b _j ∈C(R ^m),q ₁ ∈L _loc ² (R ^m),q ₁(x)≧?q*(|x|) withq*(r) monotone nondecreasing inr ando(r ²) asr → ∞, andq ₂ satisfies a mild Stummel-type condition. The point is that the assumption on the local behavior ofq ₁ is the weakest possible. The proof, unlike Simon’s original one, is of local nature and depends on a distributional inequality and elliptic estimates.     

A process of runs and its convergence to the brownian motion

Let X₁,X₂,… be i.i.d. random variables with a continuous distribution function. Let R₀=0, R_k=min{j>R_k?1, such that X_j>X_j+1}, k?1. We prove that all finite-dimensional distributions of a process $\text{W}{}^{\mathrm{(n)}}\text{(t)=}\text{(R}{}_{\mathrm{[nt]}}\text{?2[nt])}\text{2}\text{3}\text{n}\text{, t ? [0,1]}$, converge to those of the standard Brownian motion.     

Isomorphisms of Certain Locally Nilpotent Finitary Groups and Associated Rings

For any chain Γ the ring NT(Γ,K) of all finitary Γ-matrices ‖a _ij ‖ _i,jεΓ over an associative ring K with zeros on and above the main diagonal is locally nilpotent and hence radical. If R′=NT(Γ′,K′),R=NT(Γ,K) and either |Γ|<∞ or K is a ring with no zero-divisors, then isomorphisms between rings R and R′, their adjoint groups and associated Lie rings are described.     

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.     

Decomposition and approximation of multivariate functions on the cube

In this paper, we present a decomposition method of multivariate functions. This method shows that any multivariate function f on [0, 1]d is a finite sum of the form ∑jφjψj , where each φj can be extended to a smooth periodic function, each ψj is an algebraic polynomial, and each φjψj is a product of separated variable type and its smoothness is same as f . Since any smooth periodic function can be approximated well by trigonometric polynomials, using our decomposition method, we find that any smooth multivariate function on [0, 1]d can be approximated well by a combination of algebraic polynomials and trigonometric polynomials. Meanwhile, we give a precise estimate of the approximation error.