An index theory for paths that are solutions of a class of strongly indefinite variational problems

We generalize the Morse index theorem of [12,15] and we apply the new result to obtain lower estimates on the number of geodesics joining two fixed non conjugate points in certain classes of semi-Riemannian manifolds. More specifically, we consider semi-Riemannian manifolds admitting a smooth distribution spanned by commuting Killing vector fields and containing a maximal negative distribution for . In particular we obtain Morse relations for stationary semi-Riemannian manifolds (see [7]) and for the G?del-type manifolds (see [3]). Received: 4 April 2001 / Accepted: 27 September 2001 / Published online: 23 May 2002 The authors are partially sponsored by CNPq (Brazil) Proc. N. 301410/95 and N. 300254/01-6. Parts of this work were done during the visit of the two authors to the IMPA, Instituto de Matemática Pura e Aplicada, Rio de Janeiro, Brazil, in January and February 2001. The authors wish to express their gratitude to all Faculty and Staff of the IMPA for their kind hospitality.     

An acceleration scheme for cyclic subgradient projections method

An algorithm for solving convex feasibility problem for a finite family of convex sets is considered. The acceleration scheme of De Pierro (em Methodos de projeção para a resolução de sistemas gerais de equações algébricas lineares. Thesis (tese de Doutoramento), Instituto de Matemática da UFRJ, Cidade Universitária, Rio de Janeiro, Brasil, 1981), which is designed for simultaneous algorithms, is used in the algorithm to speed up the fully sequential cyclic subgradient projections method. A convergence proof is presented. The advantage of using this strategy is demonstrated with some examples.     

On the convergence properties of Hildreth's quadratic programming algorithm

We prove the linear convergence rate of Hildreth's method for quadratic programming, in both its sequential and simulateneous versions. We give bounds on the asymptotic error constant and compare these bounds to those given by Mandel for the cyclic relaxation method for solving linear inequalities.Research of this author was partially supported by CNPq grant No. 301280/86.On leave from the Universidade Federal do Rio de Janeiro, Instituto de Matemática, Rio de Janeiro, R.J. 21.910, Brazil. Research of this author was partially supported by NIH grant HL28438.     

A hierarchical model for the location of perinatal facilities in the municipality of Rio de Janeiro

We present a 3-level hierarchical model for the location of maternal and perinatal health care facilities in Rio de Janeiro. Relaxations and heuristics are developed for this model and computational results are given for problems available in the literature, for networks ranging from 10 to 400 vertices. The quality of the solutions produced by the procedures we developed do not differ significantly among themselves. The model is also applied to a case study corresponding to real 1995 data of the municipality of Rio de Janeiro.     

Load balancing and capacity constraints in a hierarchical location model

Recent work on the location of perinatal facilities in the municipality of Rio de Janeiro resulted in the development of an uncapacitated, three-level hierarchical model. An important issue that arose during the course of the research was the need to include some form of capacity constraints into the model, especially in the higher, resource intensive level of the hierarchy. This need was felt from technical discussions related to the research work and from contacts with municipality health officials.A capacitated model is presented and solved using a Lagrangean heuristic. For smaller problems optimal solutions are found using CPLEX; it is found that the heuristic usually gives high quality solutions. Next a bi-criterion model is formulated in which the additional objective measure is the imbalance in facility loading. This is solved exactly for a small problem and approximately for the 152-vertex Rio de Janeiro data.     

Hyperbolic 0–1 programming and query optimization in information retrieval

Unconstrained hyperbolic 0–1 programming can be solved in linear time when the numerator and the denominator are linear and the latter is always positive. It is NP-hard, and finding an approximate solution with a value equal to a positive multiple of the optimal one is also NP-hard, if this last hypothesis does not hold. Determining the optimal logical form of a query in information retrieval, given the attributes to be used, can be expressed as a parametric hyperbolic 0–1 program and solved in O(n logn) time, wheren is the number of elementary logical conjunctions of the attributes. This allows to characterize the optimal queries for the Van Rijsbergen synthetic criterion.This research was done in part during a visit of the first author to the Pontifical Catholic University of Rio de Janeiro in July and August 1987, sponsored by CNPq. It was also supported in part by grants 0271 and 0066 of the AFOSR to Rutgers University. The second author was with Centro de Análise de Sistemas Navais, Rio de Janeiro.     

Penalty computations for the set partitioning problem

The computation of penalties associated with the continuous relaxation of integer programming problems can be useful to derive conditional and relational tests which allow to fix some variables at their optimal value or to generate new constraints (cuts). We study in this paper the computation and the use of penalties as a tool to improve the efficiency of algorithms for solving set partitioning problems. This leads to a preprocessing scheme which can be embedded within any exact or approximate algorithm. The strength of these penalties is illustrated through computational results on some real-world set partitioning problems.This work was sponsored by FINEP (research contract number 4.3.86.0689-00), CNPq (research contract numbers 11.1592-84, 30.2281-85 and 40.2002-86.5), IBM Brazil and NSERC (grant # GP0036426).On leave from the Catholic University of Rio de Janeiro, Department of Electrical Engineering, Caixa Postal 38063, Gávea, Rio de Janeiro 22452, Brazil.     

On unconditional bases in spaces of holomorphic functions in infinite dimensions

This paper was written during the first author's stay at the Department of Mathematics of the Universidade Federal do Rio de Janeiro. He wants to thank the Department for the kind invitation and the CAPES/DAAD for its financial support.     

Conical projection algorithms for linear programming

The Linear Programming Problem is manipulated to be stated as a Non-Linear Programming Problem in which Karmarkar's logarithmic potential function is minimized in the positive cone generated by the original feasible set. The resulting problem is then solved by a master algorithm that iteratively rescales the problem and calls an internal unconstrained non-linear programming algorithm. Several different procedures for the internal algorithm are proposed, giving priority either to the reduction of the potential function or of the actual cost. We show that Karmarkar's algorithm is equivalent to this method in the special case in which the internal algorithm is reduced to a single steepest descent iteration. All variants of the new algorithm have the same complexity as Karmarkar's method, but the amount of computation is reduced by the fact that only one projection matrix must be calculated for each call of the internal algorithm.Research partly sponsored by CNPq-Brazilian National Council for Scientific and Technological Development, by National Science Foundation grant ECS-857362, Office of Naval Research contract N00014-86-K-0295, and AFOSR grant 86-0116.On leave from COPPE-Federal University of Rio de Janeiro, Cx. Postal 68511, 21941 Rio de Janeiro, RJ, Brasil.     

An algorithm to locate perinatal facilities in the municipality of Rio de Janeiro

In order to reduce infant mortality in the municipality of Rio de Janeiro it is desired to encourage all mothers-to-be to attend the appropriate health care facilities. A 3-level hierarchical prenatal–neonatal health care system is described together with a basic model for optimising accessibility to facilities. A genetic algorithm to solve the basic model is developed and some numerical experience reported. Extensions to the basic model and planned future research are briefly indicated.     

Integrating Geographical Information Systems and Multi-Criteria Methods: A Case Study

This paper presents an application of the integration between Geographical Information Systems (GIS) and Multi-Criteria Decision Analysis (MCDA) to aid spatial decisions. We present a hypothetical case study to illustrate the GIS–MCDA integration: the selection of the best municipal district of Rio de Janeiro State, Brazil, in relation to the quality of urban life. The best municipal district is the one that presents the closest characteristics to those considered ideal by the decision-maker. The approach adopted is the Multi-Objective Linear Programming (MOLP) and the chosen method is the Pareto Race.     

Descent constructions for central extensions of infinite dimensional Lie algebras

We use Galois descent to construct central extensions of twisted forms of split simple Lie algebras over rings. These types of algebras arise naturally in the construction of Extended Affine Lie Algebras. The construction also gives information about the structure of the group of automorphisms of such algebras. A. Pianzola is supported by the NSERC Discovery Grant Program. The author also wishes to thank the Instituto Argentino de Matemática for their hospitality. D. Prelat is supported by a Research Grant from Universidad CAECE.     

On contraction properties of Markov kernels

 We study Lipschitz contraction properties of general Markov kernels seen as operators on spaces of probability measures equipped with entropy-like ``distances'. Universal quantitative bounds on the associated ergodic constants are deduced from Dobrushin's ergodic coefficient. Strong contraction properties in Orlicz spaces for relative densities are proved under more restrictive mixing assumptions. We also describe contraction bounds in the entropy sense around arbitrary probability measures by introducing a suitable Dirichlet form and the corresponding modified logarithmic Sobolev constants. The interest in these bounds is illustrated on the example of inhomogeneous Gaussian chains. In particular, the existence of an invariant measure is not required in general. Received: 31 October 2000 / Revised version: 21 February 2003 / Published online: 12 May 2003 L. Miclo also thanks the hospitality and support of the Instituto de Matemática Pura e Aplicada, Rio de Janeiro, Brasil, where part of this work was done. Mathematics Subject Classification (2000): 60J05, 60J22, 37A30, 37A25, 39A11, 39A12, 46E39, 28A33, 47D07 Key words or phrases: Lipschitz contraction – Generalized relative entropy – Markov kernel – Dobrushin's ergodic coefficient – Orlicz norm – Dirichlet form – Spectral gap – Modified logarithmic Sobolev inequality – Inhomogeneous Gaussian chains – Loose of memory property     

Entire functions of exponential type bounded on the real axis and fourier transforms of distributions with bounded supports

On the complexification of the dual spaceE′ of a real Banach spaceE′ of infinite dimension, there is an entire complex valued function of exponential type, bounded onE′, hence slowly increasing onE′, which is not the Fourier transform of any distribution with bounded support onE. Partially supported by the Centro Brasileiro de Pesquisas Físicas, Rio de Janeiro, GB, Brasil and by the National Science Foundation, Washington, DC, USA. Attendance at the International Symposium on Partial Differential Equations and the Geometry of Normed Spaces was possible in part thanks to a grant from CAPES, Brasil.     

Analysing emergency medical service ambulance deployment on a Brazilian highway using the hypercube model

In this study we analyse the ambulance deployment of an emergency medical system on a Brazilian highway connecting the cities of São Paulo and Rio de Janeiro. Our focus is on the mean response time of the system to an emergency call, viewed as an important component of the user service. To evaluate the system performance we applied the hypercube model, a well-known tool for planning server-to-customer systems, which is based on spatially distributed queuing theory. The results showed that the model can be effective in supporting design and operational decisions, in particular to reduce the workload unbalancing among the ambulances.     

Practical aspects associated with location planning for maternal and perinatal assistance in Brazil

A study has been carried out aimed at reducing perinatal mortality in the municipality of Rio de Janeiro through a better distribution of health care facilities. The algorithmic aspects are detailed elsewhere and here the emphasis is on practical issues and difficulties encountered. A 3-level hierarchical model was developed. Both uncapacitated and capacitated versions are briefly described together with some results based on actual data. The project brought to light many contradictions between OR theory and practice in developing countries and, unfortunately, the models developed were not implemented by the municipality health authorities. Possible reasons for this outcome are analysed.     

Building the Additive Utility Functions for CAD-UFRJ Evaluation Staff Criteria

This paper presents an application of the UTA method for building utility functions for the evaluation criteria defined by the Staff Evaluation Commission (CAD) of the Rio de Janeiro Federal University (UFRJ). Every year, the CAD-UFRJ gives the staff evaluation results for each Postgraduate Engineering Programme. However, the method used to generate the staff evaluation is assumed unknown. Trying to find the CAD-UFRJ preference structure, the evaluation results supplied by CAD-UFRJ are used to apply the UTA method. Some additional information obtained from the CAD-UFRJ data is incorporated in the optimal solutions analysis.