Polynomial-time approximation schemes for piercing and covering with applications in wireless networks

Let be a set of disks of arbitrary radii in the plane, and let be a set of points. We study the following three problems: (i) Assuming contains the set of center points of disks in , find a minimum-cardinality subset of (if exists), such that each disk in is pierced by at least h points of , where h is a given constant. We call this problem minimum h-piercing. (ii) Assuming is such that for each there exists a point in whose distance from D's center is at most αr(D), where r(D) is D's radius and 0α<1 is a given constant, find a minimum-cardinality subset of , such that each disk in is pierced by at least one point of . We call this problem minimum discrete piercing with cores. (iii) Assuming is the set of center points of disks in , and that each covers at most l points of , where l is a constant, find a minimum-cardinality subset of , such that each point of is covered by at least one disk of . We call this problem minimum center covering. For each of these problems we present a constant-factor approximation algorithm (trivial for problem (iii)), followed by a polynomial-time approximation scheme. The polynomial-time approximation schemes are based on an adapted and extended version of Chan's [T.M. Chan, Polynomial-time approximation schemes for packing and piercing fat objects, J. Algorithms 46 (2003) 178–189] separator theorem. Our PTAS for problem (ii) enables one, in practical cases, to obtain a (1+ε)-approximation for minimum discrete piercing (i.e., for arbitrary ).     

Limits of small functors

For a small category enriched over a suitable monoidal category , the free completion of under colimits is the presheaf category . If is large, its free completion under colimits is the -category of small presheaves on , where a presheaf is small if it is a left Kan extension of some presheaf with small domain. We study the existence of limits and of monoidal closed structures on .     

Formal extension and quotients of the invariant holonomic system

Let be a semisimple Lie algebra and a Cartan subalgebra of . Fix . Let be the invariant holonomic system (see [R. Hotta, M. Kashiwara, The invariant holonomic system on a semisimple Lie algebra, Invent. Math. 75 (1984) 327–358]). First we investigate its formal extension . In the sequel we calculate the characteristic variety of some simple quotients of and its Fourier transform .     

On Jordan ideals and matrix rings

For A, a commutative ring, and results by Costa and Keller characterize certain -normalized subgroups of the symplectic group, via structures utilizing Jordan ideals and the notion of radices. The following work creates a Jordan ideal structure theorem for -graded rings, A₀A₁, and a -graded matrix algebra. The major theorem is a generalization of Costa and Keller’s previous work on matrix algebras over commutative rings.     

Levels of multi-continued fraction expansion of multi-formal Laurent series

The multi-continued fraction expansion of a multi-formal Laurent series is a sequence pair consisting of an index sequence and a multi-polynomial sequence . We denote the set of the different indices appearing infinitely many times in by H_∞, the set of the different indices appearing in by H₊, and call |H_∞| and |H₊| the first and second levels of , respectively. In this paper, it is shown how the dimension and basis of the linear space over F(z) (F) spanned by the components of are determined by H_∞ (H₊), and how the components are linearly dependent on the mentioned basis.     

Norms of some operators on the Bergman and the Hardy space in the unit polydisk and the unit ball

Let H(X) be the class of all holomorphic functions on the set and uH(X). We calculate operator norms of the multiplication operators M_u(f)=uf, on the weighted Bergman space , as well as on the Hardy space H^p(X), where X is the unit polydisk or the unit ball in . We also calculate the norm of the weighted composition operator from the weighted Bergman space , and the Hardy space , to a weighted-type space on the unit polydisk.     

The maximum edit distance from hereditary graph properties

For a graph property , the edit distance of a graph G from , denoted , is the minimum number of edge modifications (additions or deletions) one needs to apply to G in order to turn it into a graph satisfying . What is the largest possible edit distance of a graph on n vertices from ? Denote this distance by .A graph property is hereditary if it is closed under removal of vertices. In a previous work, the authors show that for any hereditary property, a random graph essentially achieves the maximal distance from , proving: with high probability. The proof implicitly asserts the existence of such , but it does not supply a general tool for determining its value or the edit distance.In this paper, we determine the values of and for some subfamilies of hereditary properties including sparse hereditary properties, complement invariant properties, (r,s)-colorability and more. We provide methods for analyzing the maximum edit distance from the graph properties of being induced H-free for some graphs H, and use it to show that in some natural cases G(n,1/2) is not the furthest graph. Throughout the paper, the various tools let us deduce the asymptotic maximum edit distance from some well studied hereditary graph properties, such as being Perfect, Chordal, Interval, Permutation, Claw-Free, Cograph and more. We also determine the edit distance of G(n,1/2) from any hereditary property, and investigate the behavior of as a function of p.The proofs combine several tools in Extremal Graph Theory, including strengthened versions of the Szemerédi Regularity Lemma, Ramsey Theory and properties of random graphs.     

Schurian vector space categories, hereditary algebras and Roiter's norm

We associate a positive real number to any vector space K-category over a field K. Generalizing a result of Nazarova and Roiter, we show that a schurian vector space K-category is representation-finite if and only if is finite and . Such vector space categories are quasilinear, i.e. its indecomposables are simple modules over their endomorphism ring. Recently, Nazarova and Roiter introduced the concept of -faithful poset in order to clarify the structure of critical posets. Their conjecture on the precise form of -faithful posets was established by Zeldich. We generalize these results and characterize -faithful quasilinear vector space K-categories in terms of a class of hereditary algebras H_ρ(D) parametrized by a skew-field D and a rational number ρ1.     

On the Brown–Shields conjecture for cyclicity in the Dirichlet space

Let be the Dirichlet space, namely the space of holomorphic functions on the unit disk whose derivative is square-integrable. We establish a new sufficient condition for a function to be cyclic, i.e. for to be dense in . This allows us to prove a special case of the conjecture of Brown and Shields that a function is cyclic in iff it is outer and its zero set (defined appropriately) is of capacity zero.     

Periodic Schur functions and slit discs

A simply connected domain is called a slit disc if minus a finite number of closed radial slits not reaching the origin. A slit disc is called rational (rationally placed) if the lengths of all its circular arcs between neighboring slits (the arguments of the slits) are rational multiples of 2π. The conformal mapping of onto , (0)=0, ^′(0)>0, extends to a continuous function on mapping it onto . A finite union E of closed non-intersecting arcs e_k on is called rational if for every k, ν_E(e_k) being the harmonic measures of e_k at ∞ for the domain . A compact E is rational if and only if there is a rational slit disc such that . A compact E essentially supports a measure with periodic Verblunsky parameters if and only if for a rationally placed . For any tuple (α₁,…,α_g+1) of positive numbers with ∑_kα_k=1 there is a finite family of closed non-intersecting arcs e_k on such that ν_E(e_k)=α_k. For any set and any >0 there is a rationally placed compact such that the Lebesgue measure |EE^*| of the symmetric difference EE^* is smaller than .     

Topological complexity is a fibrewise L–S category

Topological complexity of a space B is introduced by M. Farber to measure how much complex the space is, which is first considered on a configuration space of a motion planning of a robot arm. We also consider a stronger version of topological complexity with an additional condition: in a robot motion planning, a motion must be stasis if the initial and the terminal states are the same. Our main goal is to show the equalities and , where d(B)=B×B is a fibrewise pointed space over B whose projection and section are given by the canonical projection to the second factor and the diagonal. In addition, our method in studying fibrewise L–S category is able to treat a fibrewise space with singular fibres.     

Analyticity of functions analytic on circles

Let Δ be the open unit disc in, let pbΔ, and let f be a continuous function on which extends holomorphically from each circle in centered at the origin and from each circle in which passes through p. Then f is holomorphic on Δ.     

Iterated function systems on multifunctions and inverse problems

In this paper, we first consider the problem of defining IFS operators on the space of non-empty compact and convex subsets of . After defining a complete metric on , we construct an IFS operator and show some properties. A notable feature is the definition of a type of weak inner product on . We then define a family of complete metrics on the space of all measurable set-valued functions (with values in ), and extend the weak inner product to this space. Following this, we construct IFS operators on these spaces. We close with a brief discussion of the inverse problem of approximating an arbitrary multifunction by the attractor of an IFS.     

Stationary twists and energy minimizers on a space of measure preserving maps

Let be a bounded Lipschitz domain, a suitably quasiconvex integrand and consider the energy functional

over the space of measure preserving maps

In this paper we discuss the question of existence of multiple strong local minimizers for over . Moreover, motivated by their significance in topology and the study of mapping class groups, we consider a class of maps, referred to as twists, and examine them in connection with the corresponding Euler–Lagrange equations and investigate various qualitative properties of the resulting solutions, the stationary twists. Particular attention is paid to the special case of the so-called p-Dirichlet energy, i.e., when .     

On rank-one perturbations of normal operators

This paper is concerned with operators on Hilbert space of the form T=D+uv where D is a diagonalizable normal operator and uv is a rank-one operator. It is shown that if and the vectors u and v have Fourier coefficients and with respect to an orthonormal basis that diagonalizes D that satisfy , then T has a nontrivial hyperinvariant subspace. This partially answers an open question of at least 30 years duration.     

Projective change between two classes of -metrics

In this paper, we find equations to characterize projective change between (α,β)-metric and Randers metric on a manifold with dimension n3, where α and are two Riemannian metrics, β and are two nonzero one forms. Moreover, we consider this projective change when F has some special curvature properties.     

Tridiagonal pairs of shape (1, 2, 1)

Let denote a field and let V denote a vector space over with finite positive dimension. We consider a pair of linear transformations A:V→V and A^*:V→V that satisfies the following conditions: (i) each of A,A^* is diagonalizable; (ii) there exists an ordering of the eigenspaces of A such that A^*V_iV_i-1+V_i+V_i+1 for 0id, where V_-1=0 and V_d+1=0; (iii) there exists an ordering of the eigenspaces of A^* such that for 0iδ, where and ; (iv) there is no subspace W of V such that AWW, A^*WW, W≠0,W≠V. We call such a pair a tridiagonal pair on V. It is known that d=δ and that for 0id the dimensions of coincide; we denote this common value by ρ_i. The sequence is called the shape of the pair. In this paper we assume the shape is (1,2,1) and obtain the following results. We describe six bases for V; one diagonalizes A, another diagonalizes A^*, and the other four underlie the split decompositions for A,A^*. We give the action of A and A^* on each basis. For each ordered pair of bases among the six, we give the transition matrix. At the end we classify the tridiagonal pairs of shape (1,2,1) in terms of a sequence of scalars called the parameter array.     

There's something about the diameter

We study diameter preserving linear bijections from onto where X, Y are compact Hausdorff spaces and V, Z are Banach spaces. For instance, we obtain that if X has at least four points, Z is linearly isometric to V and either Z is a space or Z^* is strictly convex or smooth, then there is a diameter preserving linear bijection from onto if and only if X is homeomorphic to Y. We also consider the case when X and Y are not compact but locally compact spaces.     

Permutation polynomials of the form

Recently, several classes of permutation polynomials of the form (x²+x+δ)^s+x over have been discovered. They are related to Kloosterman sums. In this paper, the permutation behavior of polynomials of the form (x^p−x+δ)^s+L(x) over is investigated, where L(x) is a linearized polynomial with coefficients in . Six classes of permutation polynomials on are derived. Three classes of permutation polynomials over are also presented.     

On the sampling and recovery of bandlimited functions via scattered translates of the Gaussian

Let λ be a positive number, and let be a fixed Riesz-basis sequence, namely, (x_j) is strictly increasing, and the set of functions is a Riesz basis (i.e., unconditional basis) for L₂[−π,π]. Given a function whose Fourier transform is zero almost everywhere outside the interval [−π,π], there is a unique sequence in , depending on λ and f, such that the function

is continuous and square integrable on (−∞,∞), and satisfies the interpolatory conditions I_λ(f)(x_j)=f(x_j), . It is shown that I_λ(f)converges to f in , and also uniformly on , as λ→0⁺. In addition, the fundamental functions for the univariate interpolation process are defined, and some of their basic properties, including their exponential decay for large argument, are established. It is further shown that the associated interpolation operators are bounded on for every p[1,∞].