A greedy approximation algorithm for the group Steiner problem

In the group Steiner problem we are given an edge-weighted graph G=(V,E,w) and m subsets of vertices . Each subset g_i is called a group and the vertices in ?_ig_i are called terminals. It is required to find a minimum weight tree that contains at least one terminal from every group.We present a poly-logarithmic ratio approximation for this problem when the input graph is a tree. Our algorithm is a recursive greedy algorithm adapted from the greedy algorithm for the directed Steiner tree problem [Approximating the weight of shallow Steiner trees, Discrete Appl. Math. 93 (1999) 265-285, Approximation algorithms for directed Steiner problems, J. Algorithms 33 (1999) 73-91]. This is in contrast to earlier algorithms that are based on rounding a linear programming based relaxation for the problem [A polylogarithmic approximation algorithm for the Group Steiner tree problem, J. Algorithms 37 (2000) 66-84, preliminary version in Proceedings of SODA, 1998 pp. 253-259, On directed Steiner trees, Proceedings of SODA, 2002, pp. 59-63]. We answer in positive a question posed in [A polylogarithmic approximation algorithm for the Group Steiner tree problem, J. Algorithms 37 (2000) 66-84, preliminary version in Proceedings of SODA, 1998 pp. 253-259] on whether there exist good approximation algorithms for the group Steiner problem that are not based on rounding linear programs. For every fixed constant ε>0, our algorithm gives an approximation in polynomial time. Approximation algorithms for trees can be extended to arbitrary undirected graphs by probabilistically approximating the graph by a tree. This results in an additional multiplicative factor of in the approximation ratio, where |V| is the number of vertices in the graph. The approximation ratio of our algorithm on trees is slightly worse than the ratio of O(log(max_i|g_i|)·logm) provided by the LP based approaches.     

Open selections on smooth fans

Given a dendroid X, an open selection is an open map such that s(A)∈A for every A∈C(X). We show that a smooth fan X admits an open selection if and only if X is locally connected.     

Plancherel-Rotach asymptotics for some q-orthogonal polynomials with complex scalings

In this work we study the Plancherel-Rotach type asymptotics for Stieltjes-Wigert, q-Laguerre and Ismail-Masson orthogonal polynomials with complex scalings. The main terms of the asymptotics for Stieltjes-Wigert and q-Laguerre polynomials (Ismail-Masson polynomials) contain Ramanujan function Aq(z) for scaling parameters above the vertical line R(s)=2 (); the main terms of the asymptotics involve theta function for scaling parameters in the vertical strip 0<R(s)<2 (). When scaling parameters in the vertical strips, the number theoretical properties of scaling parameters completely determine the orders of the error terms. These asymptotic formulas may provide some insights to new random matrix models and also add a new link between special functions and number theory.     

Quasi-socle ideals and Goto numbers of parameters

Goto numbers for certain parameter ideals Q in a Noetherian local ring (A,m) with Gorenstein associated graded ring are explored. As an application, the structure of quasi-socle ideals I=Q:m^q (q≥1) in a one-dimensional local complete intersection and the question of when the graded rings are Cohen-Macaulay are studied in the case where the ideals I are integral over Q.     

Flat cyclotomic polynomials of order three

We say that a cyclotomic polynomial Φn has order three if n is the product of three distinct primes, p<q<r. Let A(n) be the largest absolute value of a coefficient of Φn. For each pair of primes p<q, we give an infinite family of r such that A(pqr)=1. We also prove that A(pqr)=A(pqs) whenever s>q is a prime congruent to .     

Configurations in abelian categories. IV. Invariants and changing stability conditions

This is the last in a series on configurations in an abelian category A. Given a finite poset (I,?), an (I,?)-configuration (σ,ι,π) is a finite collection of objects σ(J) and morphisms ι(J,K) or in A satisfying some axioms, where J,K are subsets of I. Configurations describe how an object X in A decomposes into subobjects.The first paper defined configurations and studied moduli spaces of configurations in A, using Artin stacks. It showed well-behaved moduli stacks ObjA,MA(I,?) of objects and configurations in A exist when A is the abelian category coh(P) of coherent sheaves on a projective scheme P, or mod-KQ of representations of a quiver Q. The second studied algebras of constructible functions and stack functions on ObjA.The third introduced stability conditions(τ,T,?) on A, and showed the moduli space of τ-semistable objects in class α is a constructible subset in ObjA, so its characteristic function is a constructible function. It formed algebras , , , of constructible and stack functions on ObjA, and proved many identities in them.In this paper, if (τ,T,?) and are stability conditions on A we write in terms of the , and deduce the algebras are independent of (τ,T,?). We study invariants or Iss(I,?,κ,τ) ‘counting’ τ-semistable objects or configurations in A, which satisfy additive and multiplicative identities. We compute them completely when A=mod-KQ or A=coh(P) for P a smooth curve. We also find invariants with special properties when A=coh(P) for P a smooth surface with nef, or a Calabi-Yau 3-fold.     

Configurations in abelian categories. III. Stability conditions and identities

This is the third in a series on configurations in an abelian category A. Given a finite poset (I,?), an (I,?)-configuration(σ,ι,π) is a finite collection of objects σ(J) and morphisms ι(J,K) or in A satisfying some axioms, where J,K are subsets of I. Configurations describe how an object X in A decomposes into subobjects.The first paper defined configurations and studied moduli spaces of configurations in A, using the theory of Artin stacks. It showed well-behaved moduli stacks ObjA,MA(I,?) of objects and configurations in A exist when A is the abelian category coh(P) of coherent sheaves on a projective scheme P, or mod-KQ of representations of a quiver Q. The second studied algebras of constructible functions and stack functions on ObjA.This paper introduces (weak) stability conditions(τ,T,?) on A. We show the moduli spaces , , of τ-semistable, indecomposable τ-semistable and τ-stable objects in class α are constructible sets in ObjA, and some associated configuration moduli spaces constructible in MA(I,?), so their characteristic functions and are constructible.We prove many identities relating these constructible functions, and their stack function analogues, under pushforwards. We introduce interesting algebras of constructible and stack functions, and study their structure. In the fourth paper we show are independent of (τ,T,?), and construct invariants of A,(τ,T,?).     

Improving the high order nonlinearity lower bound for Boolean functions with given algebraic immunity

Algebraic immunity is a recently introduced cryptographic parameter for Boolean functions used in stream ciphers. If pAI(f) and pAI(f⊕1) are the minimum degree of all annihilators of f and f⊕1 respectively, the algebraic immunity AI(f) is defined as the minimum of the two values. Several relations between the new parameter and old ones, like the degree, the r-th order nonlinearity and the weight of the Boolean function, have been proposed over the last few years.In this paper, we improve the existing lower bounds of the r-th order nonlinearity of a Boolean function f with given algebraic immunity. More precisely, we introduce the notion of complementary algebraic immunity defined as the maximum of pAI(f) and pAI(f⊕1). The value of can be computed as part of the calculation of AI(f), with no extra computational cost. We show that by taking advantage of all the available information from the computation of AI(f), that is both AI(f) and , the bound is tighter than all known lower bounds, where only the algebraic immunity AI(f) is used.     

The topology of the monodromy map of a second order ODE

We consider the following question: given A∈SL(2,R), which potentials q for the second order Sturm-Liouville problem have A as its Floquet multiplier? More precisely, define the monodromy map μ taking a potential q∈L²([0,2π]) to , the lift to the universal cover of SL(2,R) of the fundamental matrix map ,

     

Global well-posedness of the Cauchy problem of the fifth-order shallow water equation

By using the I-method, we prove that the Cauchy problem of the fifth-order shallow water equation is globally well-posed in the Sobolev space Hs(R) provided .     

A formula for the central value of certain Hecke L-functions

Let be the negative of a prime, and O_K its ring of integers. Let D be a prime ideal in O_K of prime norm congruent to . Under these assumptions, there exists Hecke characters ψ_D of K with conductor (D) and infinite type (1,0). Their L-series L(ψ_D,s) are associated to a CM elliptic curve A(N,D) defined over the Hilbert class field of K. We will prove a Waldspurger-type formula for L(ψ_D,s) of the form L(ψ_D,1)=Ω∑_[A],Ir(D,[A],I)m_[A],I([D]) where the sum is over class ideal representatives I of a maximal order in the quaternion algebra ramified at |N| and infinity and [A] are class group representatives of K. An application of this formula for the case N=-7 will allow us to prove the non-vanishing of a family of L-series of level 7|D| over K.     

On the monotone likelihood ratio property for the convolution of independent binomial random variables

Given that r and s are natural numbers and and are independent random variables where q,p∈(0,1), we prove that the likelihood ratio of the convolution Z=X+Y is decreasing, increasing, or constant when q<p, q>p or q=p, respectively.     

Integral point sets in higher dimensional affine spaces over finite fields

We consider point sets in the m-dimensional affine space where each squared Euclidean distance of two points is a square in Fq. It turns out that the situation in is rather similar to the one of integral distances in Euclidean spaces. Therefore we expect the results over finite fields to be useful for the Euclidean case.We completely determine the automorphism group of these spaces which preserves integral distances. For some small parameters m and q we determine the maximum cardinality I(m,q) of integral point sets in . We provide upper bounds and lower bounds on I(m,q). If we map integral distances to edges in a graph, we can define a graph Gm,q with vertex set . It turns out that Gm,q is strongly regular for some cases.     

A numerical characterization of the S2-ification of a Rees algebra

Let A be a local ring with maximal ideal . For an arbitrary ideal I of A, we define the generalized Hilbert coefficients . When the ideal I is -primary, j_k(I)=(0,…,0,(−1)^ke_k(I)), where e_k(I) is the classical kth Hilbert coefficient of I. Using these coefficients we give a numerical characterization of the homogeneous components of the S₂-ification of S=A[It,t⁻¹], extending previous results obtained by the author to not necessarily -primary ideals.     

Bernstein widths of Hardy-type operators in a non-homogeneous case

Let I=[a,b]⊂R, let 1<p?q<∞, let u and v be positive functions with u∈Lp^′(I), v∈Lq(I) and let be the Hardy-type operator given by

     

Approximation algorithms for the minimum rainbow subgraph problem

We consider the minimum rainbow subgraph problem (MRS): given a graph G, whose edges are coloured with p colours. Find a subgraph F⊆G of G of minimum order and with p edges such that each colour occurs exactly once. For graphs with maximum degree Δ(G) there is a greedy polynomial-time approximation algorithm for the MRS problem with an approximation ratio of Δ(G). In this paper we present a polynomial-time approximation algorithm with an approximation ratio of for Δ≥2.