Computational experiments with a lazy version of a <Emphasis Type="Italic">K</Emphasis> quickest simple path ranking algorithm

The quickest path problem is related to the classical shortest path problem, but its objective function concerns the transmission time of a given amount of data throughout a path, which involves both cost and capacity. The K-quickest simple paths problem generalises the latter, by looking for a given number K of simple paths in non-decreasing order of transmission time. Two categories of algorithms are known for ranking simple paths according to the transmission time. One is the adaptation of deviation algorithms for ranking shortest simple paths (Pascoal et al. in Comput. Oper. Res. 32(3):509–520, 2005; Rosen et al. in Comput. Oper. Res. 18(6):571–584, 1991), and another is based on ranking shortest simple paths in a sequence of networks with fixed capacity lower bounds (Chen in Inf. Process. Lett. 50:89–92, 1994), and afterwards selecting the K quickest ones. After reviewing the quickest path and the K-quickest simple paths problems we describe a recent algorithm for ranking quickest simple paths (Pascoal et al. in Ann. Oper. Res. 147(1):5–21, 2006). This is a lazy version of Chen’s algorithm, able to interchange the calculation of new simple paths and the output of each k-quickest simple path. Finally, the described algorithm is computationally compared to its former version, as well as to deviation algorithms.      

Orbital stability of spherical galactic models

We consider the three dimensional gravitational Vlasov Poisson system which is a canonical model in astrophysics to describe the dynamics of galactic clusters. A well known conjecture (Binney, Tremaine in Galactic Dynamics, Princeton University Press, Princeton, 1987) is the stability of spherical models which are nonincreasing radially symmetric steady states solutions. This conjecture was proved at the linear level by several authors in the continuation of the breakthrough work by Antonov (Sov. Astron. 4:859–867, 1961). In the previous work (Lemou et al. in A new variational approach to the stability of gravitational systems, submitted, 2011), we derived the stability of anisotropic models under spherically symmetric perturbations using fundamental monotonicity properties of the Hamiltonian under suitable generalized symmetric rearrangements first observed in the physics literature (Lynden-Bell in Mon. Not. R. Astron. Soc. 144:189–217, 1969; Gardner in Phys. Fluids 6:839–840, 1963; Wiechen et al. in Mon. Not. R. Astron. Soc. 223:623–646, 1988; Aly in Mon. Not. R. Astron. Soc. 241:15, 1989). In this work, we show how this approach combined with a new generalized Antonov type coercivity property implies the orbital stability of spherical models under general perturbations.     

Statistical Causality,Extremal Measures and Weak Solutions of Stochastic Differential Equations with Driving Semimartingales

In this paper we consider different concepts of causality in filtered probability spaces. Especially, we consider a generalization of a causality relationship “G is a cause of J within H ” which was first given by Mykland (1986) and which is based on Granger’s definition of causality (Granger, Econometrica 37:424–438, 1969). Then we apply this concept on weak solutions of stochastic differential equations with driving semimartingales. We also show that the given causality concept is closely connected to the concept of extremality of measures and links Granger’s causality with the concept of adapted distribution. Finally, the concept of causality is applied on solution of martingale problem.     

Distributive Lattices with a Generalized Implication: Topological Duality

In this paper we introduce the notion of generalized implication for lattices, as a binary function ⇒ that maps every pair of elements of a lattice to an ideal. We prove that a bounded lattice A is distributive if and only if there exists a generalized implication ⇒ defined in A satisfying certain conditions, and we study the class of bounded distributive lattices A endowed with a generalized implication as a common abstraction of the notions of annihilator (Mandelker, Duke Math J 37:377–386, 1970), Quasi-modal algebras (Celani, Math Bohem 126:721–736, 2001), and weakly Heyting algebras (Celani and Jansana, Math Log Q 51:219–246, 2005). We introduce the suitable notions of morphisms in order to obtain a category, as well as the corresponding notion of congruence. We develop a Priestley style topological duality for the bounded distributive lattices with a generalized implication. This duality generalizes the duality given in Celani and Jansana (Math Log Q 51:219–246, 2005) for weakly Heyting algebras and the duality given in Celani (Math Bohem 126:721–736, 2001) for Quasi-modal algebras.     

The analytic torsion of a disc

In this article, we study the Reidemeister torsion and the analytic torsion of the m dimensional disc, with the Ray and Singer homology basis (Adv Math 7:145–210, 1971). We prove that the Reidemeister torsion coincides with a power of the volume of the disc. We study the additional terms arising in the analytic torsion due to the boundary, using generalizations of the Cheeger–Müller theorem. We use a formula proved by Brüning and Ma (GAFA 16:767–873, 2006) that predicts a new anomaly boundary term beside the known term proportional to the Euler characteristic of the boundary (Lück, J Diff Geom 37:263–322, 1993). Some of our results extend to the case of the cone over a sphere, in particular we evaluate directly the analytic torsion for a cone over the circle and over the two sphere. We compare the results obtained in the low dimensional cases. We also consider a different formula for the boundary term given by Dai and Fang (Asian J Math 4:695–714, 2000), and we compare the results. The results of these work were announced in the study of Hartmann et al. (BUMI 2:529–533, 2009).     

Combinatorial Sublinear-Time Fourier Algorithms

We study the problem of estimating the best k term Fourier representation for a given frequency sparse signal (i.e., vector) A of length N≫k. More explicitly, we investigate how to deterministically identify k of the largest magnitude frequencies of [^(A)]\hat{\mathbf{A}} , and estimate their coefficients, in polynomial(k,log N) time. Randomized sublinear-time algorithms which have a small (controllable) probability of failure for each processed signal exist for solving this problem (Gilbert et al. in ACM STOC, pp. 152–161, 2002; Proceedings of SPIE Wavelets XI, 2005). In this paper we develop the first known deterministic sublinear-time sparse Fourier Transform algorithm which is guaranteed to produce accurate results. As an added bonus, a simple relaxation of our deterministic Fourier result leads to a new Monte Carlo Fourier algorithm with similar runtime/sampling bounds to the current best randomized Fourier method (Gilbert et al. in Proceedings of SPIE Wavelets XI, 2005). Finally, the Fourier algorithm we develop here implies a simpler optimized version of the deterministic compressed sensing method previously developed in (Iwen in Proc. of ACM-SIAM Symposium on Discrete Algorithms (SODA’08), 2008).     

Optimality and Duality Results for Bilevel Programming Problem Using Convexifactors

The paper is devoted to the applications of convexifactors to bilevel programming problem. Here we have defined ∂ ^∗-convex, ∂ ^∗-pseudoconvex and ∂ ^∗-quasiconvex bifunctions in terms of convexifactors on the lines of Dutta and Chandra (Optimization 53:77–94, 2004) and Li and Zhang (J. Opt. Theory Appl. 131:429–452, 2006). We derive sufficient optimality conditions for the bilevel programming problem by using these functions, and we establish various duality results by associating the given problem with two dual problems, namely Wolfe type dual and Mond–Weir type dual.     

On symbolic RG factorization of quasi-birth-and-death processes

In this paper we propose a symbolic method for solving quasi-birth-and-death processes via the RG factorization, and some “simple truncations”—see Remark 4. For reasons yet unexplained, this symbolic method yields the exact G, U, and R matrices in some low dimensional cases like the M/M/c/c retrial queue with c=1,2 servers (these results are essentially known due to Liu and Zhao (2010)), as well as the “Lie solvable model” introduced by Kawanishi (2005) (again only for c=1,2).     

Irregular abelian semigroups with weakly amenable semigroup algebra

In this paper we give counterexamples for the open problem, posed by Blackmore (Semigroup Forum 55:359–377, 1987) of whether weak amenability of a semigroup algebra ℓ ¹(S) implies complete regularity of the semigroup S. We present a neat set of conditions on a commutative semigroup (involving concepts well known to those working with semigroups, e.g. the counterexamples are nil and 0-cancellative) which ensure that S is irregular (in fact, has no nontrivial regular subsemigroup), but ℓ ¹(S) is weakly amenable. Examples are then given.     

On Constrained Nonlinear Hermite Subdivision

We determine shape-preserving regions and we describe a general setting to generate shape-preserving families for the 2-points Hermite subdivision scheme introduced by Merrien (Numer. Algorithms 2:187–200, [1992]). This general construction includes the shape-preserving families presented in Merrien and Sablonníere (Constr. Approx. 19:279–298, [2003]) and Pelosi and Sablonníere (C ¹ GP Hermite Interpolants Generated by a Subdivision Scheme, Prépublication IRMAR 06–23, Rennes, [2006]). New special families are presented as particular examples. Nonstationary and nonuniform versions of such schemes, which produce smoother limits, are discussed.      

Kalai-Smorodinsky Bargaining Solution Equilibria

Multicriteria games describe strategic interactions in which players, having more than one criterion to take into account, don’t have an a-priori opinion on the relative importance of all these criteria. Roemer (Econ. Bull. 3:1–13, 2005) introduces an organizational interpretation of the concept of equilibrium: each player can be viewed as running a bargaining game among criteria. In this paper, we analyze the bargaining problem within each player by considering the Kalai-Smorodinsky bargaining solution (see Kalai and Smorodinsky in Econometrica 43:513–518, 1975). We provide existence results for the so called Kalai-Smorodinsky bargaining solution equilibria for a general class of disagreement points which properly includes the one considered by Roemer (Econ. Bull. 3:1–13, 2005). Moreover we look at the refinement power of this equilibrium concept and show that it is an effective selection device even when combined with classical refinement concepts based on stability with respect to perturbations; in particular, we consider the extension to multicriteria games of the Selten’s trembling hand perfect equilibrium concept (see Selten in Int. J. Game Theory 4:25–55, 1975) and prove that perfect Kalai-Smorodinsky bargaining solution equilibria exist and properly refine both the perfect equilibria and the Kalai-Smorodinsky bargaining solution equilibria.     

Symmetries and First Integrals of Differential Equations

It is known that an n-dimensional system of ordinary differential equations with Lie symmetry which involves a divergence-free Liouville vector field possesses n−1 independent first integrals (i.e., it is algebraically integrable) (ünal in Phys. Lett. A 260:352–359, [1999]). In the present paper, we show that if an n-dimensional system of ordinary differential equations admits a C ^∞-symmetry vector field which satisfies some special conditions, then it also possesses n−1 independent first integrals. Several examples are given to illustrate our result. Y. Li’s research was partially supported by NSFC Grants 10531050, 10225107, SRFDP Grant 20040183030, and the 985 program of Jilin University.     

Autour des formes quadratiques indécomposables de l’image de l’homomorphisme W(F) → W(F(φ))

Let F be a field of characteristic not 2. In this article, we treat the quadratic forms of Im(W(F) → W(F(φ))) which are indecomposable, i.e., those which are not isometric to a sum of two nonzero forms of this image, where W(F) is the Witt ring of F-quadratic forms, and F(φ) is the function field of the affine quadric given by φ. This is related to the descent problems studied in [12, 14]. More precisely, we will focus on indecomposable quadratic forms of minimal dimension, which we detail for φ of dimension less than or equal to 8. We also include other related results.     

Delannoy Orthants of Legendre Polytopes

We construct an n-dimensional polytope whose boundary complex is compressed and whose face numbers for any pulling triangulation are the coefficients of the powers of (x−1)/2 in the nth Legendre polynomial. We show that the non-central Delannoy numbers count all faces in the lexicographic pulling triangulation that contain a point in a given open generalized orthant. We thus provide a geometric interpretation of a relation between the central Delannoy numbers and Legendre polynomials, observed over 50 years ago (Good in Proc. Camb. Philos. Soc. 54:39–42, 1958; Lawden in Math. Gaz. 36:193–196, 1952; Moser and Zayachkowski in Scr. Math. 26:223–229, 1963). The polytopes we construct are closely related to the root polytopes introduced by Gelfand et al. (Arnold–Gelfand mathematical seminars: geometry and singularity theory, pp. 205–221. Birkhauser, Boston, 1996).     

Stable Subconstructs: A Correction and New Results

In Lowen and Wuyts (Appl Categ Struct 8:235–245, 2000) the authors studied the simultaneously concretely reflective and concretely coreflective subconstructs of the category Ap of approach spaces. For the sake of shortness we call such subconstructs stable. Using a technique introduced in Herrlich and Lowen (1999) it was possible to explicitly describe such stable subconstructs by a condition on the objects which used certain subsets of [0, ∞ ]. Thus each stable subconstruct Ap _m described in [9] corresponds to the subset {0} ∪ [m, ∞ ] ⊂ [0, ∞ ] for m ∈ [0, ∞ ]. Although this characterization is correct, Theorem 4.7 in [9] stating that the subconstructs Ap _m were the only stable subconstructs of Ap is not. The main results, which together prove that the only stable subconstructs are those where a restriction is put on the range of the distances of the objects, are upheld, but it turns out that not only the sets {0} ∪ [m, ∞ ], but actually each closed subsemigroup of [0, ∞ ] determines a stable subconstruct (albeit again in exactly the same way as characterized in [9]). In the first part of our paper, Sections 1 and 2, we develop the general technique, which is totally different to the one from [3], and in Theorem 2.13 we prove the main result for the case of approach spaces. The technique which we develop is also applicable to other cases. Thus, in Section 3, more precisely in Theorems 3.9 and 3.11, we give the complete solution to the corresponding characterization problem for the constructs pq Met ^∞ of pseudo-quasi-metric spaces and p Met ^∞ of pseudometric spaces and in Section 4 we briefly sketch how the technique can be adapted and used to also completely solve the problem in the case of more general types of approach spaces and metric spaces. At the same time, in all cases, we are able to give necessary and sufficient conditions under which two stable subconstructs of one of these topological constructs are concretely isomorphic. It turns out that in all cases there are 2^à₀2^{\aleph_0} non-concretely isomorphic stable subconstructs.     

The negative cycles polyhedron and hardness of checking some polyhedral properties

Given a graph G=(V,E) and a weight function on the edges w:E→ℝ, we consider the polyhedron P(G,w) of negative-weight flows on G, and get a complete characterization of the vertices and extreme directions of P(G,w). Based on this characterization, and using a construction developed in Khachiyan et al. (Discrete Comput. Geom. 39(1–3):174–190, 2008), we show that, unless P=NP, there is no output polynomial-time algorithm to generate all the vertices of a 0/1-polyhedron. This strengthens the NP-hardness result of Khachiyan et al. (Discrete Comput. Geom. 39(1–3):174–190, 2008) for non 0/1-polyhedra, and comes in contrast with the polynomiality of vertex enumeration for 0/1-polytopes (Bussiech and Lübbecke in Comput. Geom., Theory Appl. 11(2):103–109, 1998). As further applications, we show that it is NP-hard to check if a given integral polyhedron is 0/1, or if a given polyhedron is half-integral. Finally, we also show that it is NP-hard to approximate the maximum support of a vertex of a polyhedron in ℝ ⁿ within a factor of 12/n.     

Generalized Cayley graphs of semigroups II

Following Zhu (Semigroup Forum, 2011, doi:), we study generalized Cayley graphs of semigroups. The Cayley D-saturated property, a particular combinatorial property, of generalized Cayley graphs of semigroups is considered and most of the results in Kelarev and Quinn (Semigroup Forum 66:89–96, 2003), Yang and Gao (Semigroup Forum 80:174–180, 2010) are extended. In addition, for some basic graphs and their complete fission graphs, we describe all semigroups whose universal Cayley graphs are isomorphic to these graphs.     

Spiral Anchoring in Media with Multiple Inhomogeneities: A Dynamical System Approach

The spiral is one of nature’s more ubiquitous shapes: It can be seen in various media, from galactic geometry to cardiac tissue. Mathematically, spiral waves arise as solutions to reaction–diffusion partial differential equations (RDS). In the literature, various experimentally observed dynamical states and bifurcations of spiral waves have been explained using the underlying Euclidean symmetry of the RDS—see for example (Barkley in Phys. Rev. Lett. 68:2090–2093, 1992; Phys. Rev. Lett. 76:164–167, 1994; Sandstede et al. in C. R. Acad. Sci. 324:153–158, 1997; J. Differ. Equ. 141:122–149, 1997; J. Nonlinear Sci. 9:439–478, 1999), or additionally using the concept of forced Euclidean symmetry-breaking for situations where an inhomogeneity or anisotropy is present—see (LeBlanc in Nonlinearity 15:1179–1203, 2002; LeBlanc and Wulff in J. Nonlinear Sci. 10:569–601, 2000). In this paper, we further investigate the role of medium inhomogeneities on spiral wave dynamics by considering the effects of several localized sites of inhomogeneity. Using a model-independent approach based on n>1 simultaneous translational symmetry-breaking perturbations of the dynamics near rotating waves, we fully characterize the local anchoring behavior of the spiral wave in the n-dimensional parameter space of relative “amplitudes” of the individual perturbations. For the case n=2, we supplement the local anchoring results with a classification of the generic one-parameter bifurcation diagrams of anchored states which can be obtained by circling the origin of the two-dimensional amplitude parameter space. Numerical examples are given to illustrate our various results.