A method for the resolution of the Jacobi equation <Emphasis Type="Italic">Y</Emphasis>″ + <Emphasis Type="Italic">RY</Emphasis> = 0 on the manifold <Emphasis Type="Italic">Sp</Emphasis>(2)/<Emphasis Type="Italic">SU</Emphasis>(2)

In this paper a method for the resolution of the differential equation of the Jacobi vector fields in the manifold V ₁ = Sp(2)/SU(2) is exposed. These results are applied to determine areas and volumes of geodesic spheres and balls. Work partially supported by DGI (Spain) and FEDER Projects MTM 2004-06015-C02-01 and MTM 2007-65852 (first author) and by Research Project PGIDIT05PXIB16601PR (second author). Authors’ addresses: A. M. Naveira, Departamento de Geometría y Topología. Facultad de Matemáticas, Avda. Andrés Estellés, N1, 46100 – Burjassot, Valencia, Spain; A. D. Tarrío Tobar, E. U. Arquitectura Técnica, Campus A Zapateira. Universidad de A Coru?a, 15192 – A Coru?a, Spain     

Restart strategies for GRASP with path-relinking heuristics

GRASP with path-relinking is a hybrid metaheuristic, or stochastic local search (Monte Carlo) method, for combinatorial optimization. A restart strategy in GRASP with path-relinking heuristics is a set of iterations {i ₁, i ₂, …} on which the heuristic is restarted from scratch using a new seed for the random number generator. Restart strategies have been shown to speed up stochastic local search algorithms. In this paper, we propose a new restart strategy for GRASP with path-relinking heuristics. We illustrate the speedup obtained with our restart strategy on GRASP with path-relinking heuristics for the maximum cut problem, the maximum weighted satisfiability problem, and the private virtual circuit routing problem.     

Computing optimal preemptive schedules for parallel tasks: linear programming approaches

 We study the problem of scheduling a set of n independent parallel tasks on m processors, where in addition to the processing time there is a size associated with each task indicating that the task can be processed on any subset of processors of the given size. Based on a linear programming formulation, we propose an algorithm for computing a preemptive schedule with minimum makespan, and show that the running time of the algorithm depends polynomially on m and only linearly on n. Thus for any fixed m, an optimal preemptive schedule can be computed in O(n) time. We also present extensions of this approach to other (more general) scheduling problems with malleable tasks, due dates and maximum lateness minimization. Received: November 1999 / Accepted: November 2002 Publication online: December 19, 2002 RID="⋆" ID="⋆" This work was done while the authors were associated with the research institutes IDSIA Lugano and MPII Saarbrücken and were supported in part by the Swiss Office Fédéral de l'éducation et de la Science project n 97.0315 titled ``Platform' and by EU ESPRIT LTR Project No. 20244 (ALCOM-IT)     

Convergence of a class of degenerate Ginzburg-Landau functionals and regularity for a subelliptic harmonic map equation

In this paper, we consider a class of Ginzburg-Landau functionalsE _ε associated with a couple of non-commuting vector fields which yield a “degenerate” energy. We study the asymptotic behavior of the minimizers, showing that it does not depend on the topological degree of the boundary datum; and we prove uniqueness and regularity of the minimizer of the limit problem, in spite of the lack of lifting theorems in the natural function spaces for the limit functional.

---

Résumé  Dans cet article, nous considérons une classe de fonctionnellesE _ε du type Ginzburg-Landau associée a un couple de champs de vecteurs définissant une énergie dégénérée. Nous étudions le comportement asymptotique des minimiseurs. Nous démontrons que ce comportement ne dépend pas du degré topologique de la donnée a la frontiere et nous prouvons l’unicité et la régularité du minimiseur du probléme limite, malgré l’absence d’un théorème de lifting dans les espaces de Sobolev naturels pour la même fonctionnelle.

---

---

The authors were supported by University of Bologna, funds for selected research topics, and by GNAMPA of the INDAM, Italy, project “Analysis in metric spaces and subelliptic equations.”     

Invariants de classes : exemples de non-annulation en dimension supérieure

The so-called class-invariant homomorphism ψ measures the Galois module structure of torsors—under a finite flat group scheme G—which lie in the image of a coboundary map associated to an isogeny between (Néron models of) abelian varieties with kernel G. When the varieties are elliptic curves with semi-stable reduction and the order of G is coprime to 6, it is known that the homomorphism ψ vanishes on torsion points. In this paper, using Weil restrictions of elliptic curves, we give the construction, for any prime number p > 2, of an abelian variety A of dimension p endowed with an isogeny (with kernel μ _p ) whose coboundary map is surjective. In the case when A has rank zero and the p-part of the Picard group of the base is non-trivial, we obtain examples where ψ does not vanish on torsion points.

---

Résumé  Le class-invariant homomorphism permet de mesurer la structure galoisienne des torseurs—sous un schéma en groupes fini et plat G—qui sont dans l’image du cobord associé à une isogénie, de noyau G, entre des (modèles de Néron de) variétés abéliennes. Quand les variétés sont des courbes elliptiques à réduction semi-stable et que l’ordre de G est premier à 6, on sait que cet homomorphisme s’annule sur les points de torsion. Dans cet article, en nous servant de restrictions de Weil de courbes elliptiques, nous construisons, pour tout nombre premier p > 2, une variété abélienne A de dimension p munie d’une isogénie (de noyau μ _p ) dont le cobord est surjectif. Si A est de rang nul, et si la p-partie du groupe de Picard de la base est non triviale, nous obtenons ainsi un exemple où le class-invariant homomorphism ne s’annule pas sur les points de torsion.

     

A Lagrangean relaxation heuristic for vehicle routing

This paper presents a new heuristic algorithm for the vehicle routing problem (VRP) which makes use of Lagrangean relaxation to transform the VRP into a modified m-traveling salesman problem. Application of the proposed algorithm to test problems from the literature has produced new best-known solutions.     

Espaces de Thom et contre-exemples de J.L. Verdier et M. Goresky

Résumé SoitS une variété algébrique complexe singulière, de dimension réelle 2s. M.H. Schwartz et R. Mac-Pherson ont défini des classes caractéristiques, généralisation des classes de Chern, dans l'homologie deS (de telles classes n'existent pas en cohomologie). D'autre part l'homomorphisme de PoincaréH ^2s−⋆ (S)→H _⋆ (S) n'est en géneral, ni injectif, ni surjectif. Cet homomorphisme se factorise par l'homologie d'intersectionIH _⋆ (S). Il est naturel de se demander quel est le “comportement” des classes deS (classes de M.H. Schwartz-R. Mac-Pherson) vis-à-vis du morphisme canonique α:IH _⋆(S)→H_⋆(S). J. L. Verdier a construit un exemple dans lequel, le morphisme canonique α n'étant pas injectif, les classes deS peuvent ètre réalisées de plusieurs manières comme images de classes de Chern de variétés lisses, désingularisations deS, et dont l'homologie est isomorphe àIH _⋆ (S). M. Goresky a construit une variation de cet exemple dans laquelle les classes de Chern ne sont pas dans l'image de α. Nous montrons que ces deux exemples sont cas particuliers d'une même situation:S est un espace de Thom associé à un plongement d'une variétéB dans un espaceIP ^k . L'essentiel de cet article a été écrit lors d'un séjour des auteurs à l'Université du Rio Grande do Sul (Porto-Alegre-Brésil), sur invitation de M. Sebastiani. Nous le remercions ici, ainsi que l'Université de Porto-Alegre, de leur accueil et de leur hospitalité      

Solving the Vehicle Routing Problem with Stochastic Demands using the Cross-Entropy Method

An alternate formulation of the classical vehicle routing problem with stochastic demands (VRPSD) is considered. We propose a new heuristic method to solve the problem, based on the Cross-Entropy method. In order to better estimate the objective function at each point in the domain, we incorporate Monte Carlo sampling. This creates many practical issues, especially the decision as to when to draw new samples and how many samples to use. We also develop a framework for obtaining exact solutions and tight lower bounds for the problem under various conditions, which include specific families of demand distributions. This is used to assess the performance of the algorithm. Finally, numerical results are presented for various problem instances to illustrate the ideas.     

Type des orbites périodiques des flots associés à des lagrangiens optiques homogènes

Résumé. Soit L : T M → ℝ un lagrangien optique et homogène dans la fibre défini sur le fibré tangent d’une variété orientable de dimension n et γ un lacet régulier 1-périodique qui est un point critique non dégénéré d’indice p de l’action lagrangienne associée à L (il lui correspond alors un point périodique (x, v) du flot d’Euler-Lagrange (φ_t )). Soit T une transversale en (x, v) au champ de vecteurs dans la surface d’énergie et P l’application de premier retour de Poincaré dans cette transversale; on montre alors que le nombre de Lefschetz pour P en (x, v) est (−1)^n−1+p. On en déduit que si 2n_h est le nombre de multiplicateurs de Floquet réels strictement positifs et non nuls, alors: n_h = n − 1 + p (mod 2). On explique comment déduire qu’un lagrangien optique quelconque défini sur le fibré tangent d’une variété orientable compacte de dimension paire de π₁ non trivial a une une orbite périodique qui est soit dégénérée, soit a un exposant de Floquet hyperbolique dans tout niveau d’énergie au dessus du niveau critique de Ma?é.      

Algebraic leaves of algebraic foliations over number fields

Summary — We prove an algebraicity criterion for leaves of algebraic foliations defined over number fields. Namely, consider a number field K embedded in C, a smooth algebraic variety X over K, equipped with a K-rational point P, and F an algebraic subbundle of the its tangent bundle T_X, defined over K. Assume moreover that the vector bundle F is involutive, i.e., closed unter Lie bracket. Then it defines an holomorphic foliation of the analytic mainfold X(C), and one may consider its leaf ℱ through P. We prove that ℱ is algebraic if the following local conditions are satisfied: i) For almost every prime ideal p of the ring of integers 𝒪_K of the number field K, the p-curvature of the reduction modulo p of the involutive bundle F vanishes at P (where p denotes the characteristic of the residue field 𝒪_K / p ). ii) The analytic manifold ℱ satisfies the Liouville property; this arises, in particular, if ℱ is the image by some holomorphic map of the complement in a complex algebraic variety of a closed analytic subset. This algebraicity criterion unifies and extends various results of D. V. and G. V. Chudnovsky, André, and Graftieaux, and also admits new consequences. For instance, applied to an algebraic group G over K, it shows that a K-Lie subalgebra h of Lie G is algebraic if and only if for almost every non-zero prime ideal p of 𝒪_K , of residue characteristic p, the reduction modulo p of h is a restricted Lie subalgebra of the reduction modulo p of Lie G (i.e., is stable under p-th powers). This solves a conjecture of Ekedahl and Shepherd-Barron. The algebraicity criterion above follows from a more basic algebraicity criterion concerning smooth formal germs in algebraic varieties over number fields. The proof of the latter relies on “transcendence techniques”, recast in a modern geometric version involving elementary concepts of Arakelov geometry, and on some analytic estimates, related to the First Main Theorem of higher-dimensional Nevanlinna theory.

---

Résumé — Nous établissons un critère d'algébricité concernant les feuilles des feuilletages algébriques définis sur un corps de nombres. Soit en effet K un corps de nombres plongé dans C, X une variété algébrique lisse sur K, munie d'un point K-rationnel P, et F un sous-fibré du fibré tangent T_X, défini sur K. Supposons de plus que le fibré vectoriel F soit involutif, i.e.., stable par crochet de Lie. Il définit alors un feuilletage holomorphe de la variété analytique X(C) et l'on peut considérer la feuille ℱ de ce feuilletage passant par P. Nous montrons que ℱ est algébrique lorque les conditions locales suivantes son satisfaites: i) Pour presque tout idéal premier p de l'annneau des entiers 𝒪_K de K, la réduction modulo p du fibré F est stablé par l'opération de puissance p-ième (où p désigne la caractéristique du corps résiduel 𝒪_K / p ). ii) La variété analytique ℱ satisfait à la propriété de Liouville; cela a lieu, par exemple, lorsque ℱ est l'image par une application holomorphe du complémentaire d'un sous-ensemble analytique fermé dans une variété algébrique. Ce critère d'algébricité unifie et généralise divers résultats de D. V. and G. V. Chudnovsky, André et Graftieaux. Il conduit aussi à de nouvelles conséquences. Par exemple, appliqué à un groupe algébrique G sur K, il montre qu'une sous-algèbre de Lie h de Lie G, définie sur K, est algébrique si et seulement si, pour presque tout idéal premier p de 𝒪_K , de caractéristique résiduelle p, la réduction modulo p de h est une sous-p-algèbre de Lie de la réduction modulo p de Lie G (i.e., est stable par puissance p-ième). Cet énoncé résout une conjecture d'Ekedahl et Shepherd-Barron. Le critère d'algébricité ci-dessus découle d'un critère d'algébricité plus général, concernant les germes de sous-variétés formelles des variétés sur les corps de nombres. La démonstration de ce dernier repose sur des “techniques de transcendance”, reformulées dans une version géométrique utilisant diverses notions élémentaires de géométrie d'Arakelov, et sur des estimations analytiques reliées au premier théorème fondamental de la théorie de Nevanlinna en dimension supérieure.

---

---

Manucsrit re?u le 27 septembre 2000.     

Problèmes de modules pour les formes différentielles singulières dans le plan complexe

Resumé On considère des équations de Pfaff holomorphes à l’origine de ℂ², ω=a(x, y)dx +b(x, y)dy. Sous des hypothèses génériques, portant sur le premier jet non nulω _v deω, on décrit explicitement l’espace des modules de ω pourv petit. On s’intéresse aussi aux formes rigides et aux problèmes sous-jacents à ce type de question, notemment l’invariance topologique de l’holonomie projective.

---

We consider holomorphic Pfaffian equations ω=a(x, y)dx +b(x, y)dy. Under generic assumptions on the first significant jet of ω, we describe the space of moduli for Pfaffian equations of small order. Problems of rigidity and topological invariance of projective holonomy are also studied.

---

---

Une partie de ce travail a été réalisé lors d’un séjour du premier auteur à l’IMPA de Rio et à l’Université Fédérale du Minas Gerais. Ceci grace au concours du CNPQ (Brésil) et du Ministère des Relations Extérieures (France).     

Une procédure de Calderón-Zygmund pour le problème de la racine <Emphasis Type="Italic">k</Emphasis>-ième

Soit f une fonction définie sur un ouvert de ℝ ^d , à valeurs positives ou nulles, de classe C ^k , où k est un entier ≥2. Un résultat de Colombini–Jannelli–Spagnolo assure que ∇(f ^{1/ k} ) appartient à L ¹ _loc. Nous démontrons ici que ∇(f ^{1/ k} )∈L _w ^{k / k −2}, ce qui fournit une amélioration optimale du résultat ci-dessus et une généralisation d’un théorème classique de Glaeser sur la racine carrée. La méthode de preuve requiert l’usage d’une décomposition de Calderón–Zygmund de la fonction f qui nous permet de nous ramener à des formes normales de manipulation simple. Nous montrons également que la régularité C ^k est essentiellement nécessaire au résultat. Nous donnons quelques applications à des problèmes d’équations aux dérivées partielles faiblement hyperboliques. L’adaptabilité des méthodes de décomposition de Calderón-Zygmund, utilisées en analyse harmonique et pseudo-différentielle, trouve dans ces résultats une nouvelle illustration.

---

---

Received: December 13, 2001?Published online: April 14, 2003     

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).     

An effective heuristic for large-scale capacitated facility location problems

The Capacitated Facility Location Problem (CFLP) consists of locating a set of facilities with capacity constraints to satisfy the demands of a set of clients at the minimum cost. In this paper we propose a simple and effective heuristic for large-scale instances of CFLP. The heuristic is based on a Lagrangean relaxation which is used to select a subset of “promising” variables forming the core problem and on a Branch-and-Cut algorithm that solves the core problem. Computational results on very large scale instances (up to 4 million variables) are reported.     

Multilevel Monte Carlo for stochastic differential equations with additive fractional noise

We adopt the multilevel Monte Carlo method introduced by M. Giles (Multilevel Monte Carlo path simulation, Oper. Res. 56(3):607–617, 2008) to SDEs with additive fractional noise of Hurst parameter H>1/2. For the approximation of a Lipschitz functional of the terminal state of the SDE we construct a multilevel estimator based on the Euler scheme. This estimator achieves a prescribed root mean square error of order ε with a computational effort of order ε ⁻².     

Lifting chains of prime ideals to paravaluation rings

Résumé  SoitR ⊂T une extension des anneaux commutatifs et soit {P _α :α ∈I} une cha?ne croissante des idéaux premiers deR (I étant un ensemble totalement ordonné, peut-être infini). Alors il existe un anneau de paravaluationV deT et une cha?ne {Q _α} des idéaux premiers deV de sorte queR ⊂V etQ _α ∩R =P _α pour toutα ∈I. Tout d’abord, on établit le cas spécial dans lequelT est un corps; dans ce cas, on trouve en effet un tel anneau de valuationV deT. Ensuite, l’assertion ci-dessus pour le cas général découle comme conséquence. Dans le cas général, on peut aussi remplacer le mot “paravaluation” avec le mot “valuation” siR est un anneau de Marot etT est son anneau total de fractions.      

On the convergence of the Weiszfeld algorithm

In this work we analyze the paper “Brimberg, J. (1995): The Fermat-Weber location problem revisited. Mathematical Programming 71, 71–76” which claims to close the question on the conjecture posed by Chandrasekaran and Tamir in 1989 on the convergence of the Weiszfeld algorithm. Some counterexamples are shown to the proofs showed in Brimberg’s paper. Received: January 1999 / Accepted: December 2001?Published online April 12, 2002 RID="*" ID="*"Partially supported by PB/11/FS/97 of Fundación Séneca of the Comunidad Autónoma de la Región de Murcia RID="**" ID="**"Plan Nacional de Investigación Científica, Desarrollo e Innovación Tecnológica (I+I+D), project TIC2000-1750-C06-06 RID="*" RID="**"