Chord calculus and stochastic geometry

Chord calculus is a collection of integration procedures applied to to the combinatorial decompositions that give the solution of the Buffon-Sylvester problem for n needles in a plane or the similar problem in IR ³. It is a source of various integral geometry identities, some of which find their application in Stochastic geometry. In the present paper these applications are focused on random convex polygons and polyhedrons, where we define certain classes where rather simple tomography analysis is possible. The choice of these classes (the Independent Angles class and the Independent Orientations class) is due to the nature of the results of the Chord calculus. The last section points at an application of the convex polygons from the Independent Angles class to Boolean sets in the plane (Boolean models) whose probability distibutions are invariant with respect to the group of Euclidean motions of the plane.     

Combinatorial optimization - Polyhedra and efficiency: A book review

We review the recent three-volume monograph authored by Alexander Schrijver, Combinatorial Optimization - Polyhedra and Efficiency, Springer-Verlag, 2003, ISBN 3-540-44389-4, 1881 pages (in a slip-case), price: € 89,95 .Received: November 2003, Revised: January 2004, AMS classification: 90C57, 68R10, 05C99     

Combinatorial approximation algorithms: a comparative review

This paper is a comparative review of three related books:Giorgio Ausiello, Pierluigi Crescenzi, Giorgio Gambosi, Viggo Kann, Alberto Marchetti-Spaccamela, Marco Protasi, Complexity and Approximation (Combinatorial Optimization Problems and Their Approximability Properties), second printing, Springer, Berlin, 2003, ISBN 3-540-65431-3, 524 pp., €53.45 (first printing 1999).Juraj Hromkovi?, Algorithmics for Hard Problems (Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics), second edition, Springer, Berlin, 2003, ISBN 3-540-44134-4, 544 pp., €53.45 (first printing 2001).Vijay Vazirani, Approximation Algorithms, second printing, Springer, Berlin, 2002, ISBN 3-540-65367-8, 380 pp., €37.40 (first printing 2001).     

A bivariate exponential distribution arising in random geometry

Summary In this paper a new bivariate exponential distribution, arising naturally in the theory of Poisson line processes, is studied. The distribution has some interesting and useful properties which renders it suitable for use in statistical modelling work. It is presented in the spirit of adding to the repertoire of bivariate exponential forms. It joins other models, such as those of Downton (1970,J. R. Statist. Soc., B,32, 408–417), Marshall and Olkin (1967,J. Appl. Prob.,4, 291–302) and Nagao and Kadoya (1971,Bulletin of the Disaster Prevention Research Institute,20, 3, 183–215), which have their origins in the theory of stochastic processes.     

Multi-policy improvement in stochastic optimization with forward recursive function criteria

Iwamoto recently established a formal transformation via an invariant imbedding to construct a controlled Markov chain that can be solved in a backward manner, as in backward induction for finite-horizon Markov decision processes (MDPs), for a given controlled Markov chain with non-additive forward recursive objective function criterion. Chang et al. presented formal methods, called “parallel rollout” and “policy switching,” of combining given multiple policies in MDPs and showed that the policies generated by both methods improve all of the policies that the methods combine. This brief paper extends the methods of parallel rollout and policy switching for forward recursive objective function criteria and shows that the similar property holds as in MDPs. We further discuss how to implement these methods via simulation.     

Exchangeable random measures in the plane

A random measure on [0,1]², [0, 1]}₊ or ₊ ² is said to be separately exchangeable, if its distribution is invariant under arbitrary Lebesgue measure-preserving transformations in the two coordinates, and jointly exchangeable if is defined on [0,1]² or ₊ ² , and its distribution is invariant under mappings by a common measure-preserving transformation in both directions. In each case, we derive a general representation of in terms of independent Poisson processes and i.i.d. random variables.     

A commentary on the method of successive starts

A number of comments are made on the method of successive starts. These include a derivation of the method, a discussion of it in its most general setting, remarks on its use, suggestions to improve its accuracy, and some open questions about the method. Several numerical examples are discussed illustrating both success and failure with the method.     

State-space stochastic volatility models: A review of estimation algorithms

Stochastic volatility models (SVMs) represent an important framework for the analysis of financial time series data, together with ARCH-type models; but unlike the latter, the former, at least from the statistical point of view, cannot rely on the possibility of obtaining exact inference, in particular with regard to maximum likelihood estimates for the parameters of interest. For SVMs, usually only approximate results can be obtained, unless particularly sophisticated estimation strategies like exact non-gaussian filtering methods or simulation techniques are employed. In this paper we review SVM and present a new characterization for them, called ‘generalized bilinear stochastic volatility’. © 1996 John Wiley & Sons, Ltd.     

Tomography models of random convex polygons

Combinatorial integral geometry possesses some results that can be interpreted as belonging to the field of Geometric Tomography. The main purpose of the present paper is to present a case of parallel X-ray approach to tomography of random convex polygons. However, the Introduction reviews briefly some earlier results by the author that refer to reconstruction of (non-random) convex domains by means of a point X-ray. The main tool in treating the parallel X-rays is disintegrated Pleijel identity, or rather, its averaged version, whose derivation is represented in complete detail. The paper singles out a class of random polygons called tomography models, that offer essential advantages for the analysis. The definition of a tomography model is given in terms of stochastic independence. Fortunately, random translation-invariant Poisson processes of lines in IR ² suggest a class of examples. We recall that each such line process is determined by its rose of directions ρ(?). For rather general ρ(?), the number weighted typical polygon in the polygonal partition of the plane generated by the corresponding Poisson line process happens to be a tomography model. For general tomography models, a differential equation is derived for the Laplace transform for parallel X-rays, that rises several interesting computational problems.     

A modification of the invariant imbedding method for a singular boundary value problem

We consider a dynamically-consistent analytical model of a 3D topographic vortex. The model is governed by equations derived from the classical problem of the axisymmetric Taylor–Couette flow. Using linear expansions, these equations can be reduced to a differential sixth-order equation with variable coefficients. For this differential equation, we formulate a boundary value problem, which has a number of issues for numerical solving. To avoid these issues and find the eigenvalues and eigenfunctions of the boundary value problem, we suggest a modification of the invariant imbedding method (the Riccati equation method). In this paper, we show that such a modification is necessary since the boundary conditions possess singular matrices, which sufficiently complicate the derivation of the Riccati equation. We suggest algebraic manipulations, which permit the initial problem to be reduced to a problem with regular boundary conditions. Also, we propose a method for obtaining a numerical solution of the matrix Riccati equation by means of recurrence relations, which allow us to obtain a matrizer converging to the required eigenfunction. The suggested method is tested by calculating the corresponding eigenvalues and eigenfunctions, and then, by constructing fluid particle trajectories on the basis of the eigenfunctions.     

非光滑凸规划的割平面法及其在组合优化中的应用

本文利用次梯度构造了一种割平面 ,将非光滑凸规划松驰为光滑规划 ,给出了一种非光滑凸规划的割平面法 ,并证明了其收敛性 ,通过在组合优化中的应用说明该算法是有效的 .     

Some theoretical challenges in digital geometry: A perspective

In recent years image analysis has become a research field of exceptional significance, due to its relevance to real life problems in important societal and governmental sectors, such as medicine, defense, and security. The explicit purpose of the present Perspective is to suggest a number of strategic objectives for theoretical research, with an emphasis on the combinatorial approach in image analysis. Most of the proposed objectives relate to the need to make the theoretical foundations of combinatorial image analysis better integrated within a number of well-established subjects of theoretical computer science and discrete applied mathematics, such as the theory of algorithms and problem complexity, combinatorial optimization and polyhedral combinatorics, integer and linear programming, and computational geometry.     

一类组合公式及B-型算子矩量

给出几组组合公式，由此得出Bernstein算子、Bernsten-Eantorovich算子、DurrmeyerBernstein算子和修正Durrmeyer－Bernstein算子轻量及中心知量的计算公式．     

Equivariant mappings: a new approach in stochastic simulations

Stochastic simulations on manifolds usually are traced back to ⁿ via charts. If a group G is acting on a manifold M and if the respective distribution v is invariant under this group action then in many cases of practical interest there exists a more convenient approach which uses equivariant mappings. The concept of equivariant mappings will be discussed intensively at the instance of the Grassman manifold in which case G equals the orthogonal group. Further advantages of this concept will be demonstrated by applying it to a probabilistic problem from the field of combinatorial geometry.     

The school bus routing problem: A review

This paper aims to provide a comprehensive review of the school bus routing problem (SBRP). SBRP seeks to plan an efficient schedule for a fleet of school buses where each bus picks up students from various bus stops and delivers them to their designated schools while satisfying various constraints such as the maximum capacity of a bus, the maximum riding time of a student in a bus, and the time window of a school. This class of problem consists of different sub-problems involving data preparation, bus stop selection, bus route generation, school bell time adjustment, and bus scheduling. In this paper, the various assumptions, constraints, and solution methods used in the literature on SBRP are summarized. A list of issues requiring further research is also presented.     

A connection between cutting plane theory and the geometry of numbers

In this paper, we relate several questions about cutting planes to a fundamental problem in the geometry of numbers, namely, the closest vector problem. Using this connection we show that the dominance, membership and validity problems are NP-complete for Chvátal and split cuts. Received: August 28, 2001 / Accepted: March 2002?Published online May 8, 2002     

A parameterization method for the computation of invariant tori and their whiskers in quasi-periodic maps: Rigorous results

In this paper we prove rigorous results on persistence of invariant tori and their whiskers. The proofs are based on the parameterization method of [X. Cabré, E. Fontich, R. de la Llave, The parameterization method for invariant manifolds. I. Manifolds associated to non-resonant subspaces, Indiana Univ. Math. J. 52 (2) (2003) 283-328; X. Cabré, E. Fontich, R. de la Llave, The parameterization method for invariant manifolds. II. Regularity with respect to parameters, Indiana Univ. Math. J. 52 (2) (2003) 329-360]. The invariant manifolds results proved here include as particular cases of the usual (strong) stable and (strong) unstable manifolds, but also include other non-resonant manifolds. The method lends itself to numerical implementations whose analysis and implementation is studied in [A. Haro, R. de la Llave, A parameterization method for the computation of invariant tori and their whiskers in quasi-periodic maps: Numerical algorithms, preprint, 2005; A. Haro, R. de la Llave, A parameterization method for the computation of invariant tori and their whiskers in quasi-periodic maps: Numerical implementation and examples, preprint, 2005]. The results are stated as a posteriori results. Namely, that if one has an approximate solution which is not degenerate, then, one has a true solution not too far from the approximate one. This can be used to validate the results of numerical computations.