The Transit Route Arc-Node Service Maximization problem

This article presents a new method for determining optimal transit routes. The Transit Route Arc-Node Service Maximization model is a mathematical model that maximizes the service value of a route, rather than minimizing cost. Cost (distance) is considered as a budget constraint on the extent of the route. The mathematical formulation modifies and exploits the structure of linear programming problems designed for the traveling salesman problem. An innovative divide-and-conquer solution procedure is presented that not only makes the transit routing problem tractable, but also provides a range of high-quality alternate routes for consideration, some of which have substantially varying geometries. Variant formulations are provided for several common transit route types. The model is tested through its application to an existing street network in Richardson, TX. Optimal numeric results are obtained for several problem instances, and these results demonstrate that increased route cost is not correlated with increased service provision.     

On the sequence of powers of a stochastic matrix with large exponent

We consider the class of primitive stochastic n×n matrices A, whose exponent is at least (n²−2n+2)/2+2. It is known that for such an A, the associated directed graph has cycles of just two different lengths, say k and j with k>j, and that there is an α between 0 and 1 such that the characteristic polynomial of A is λⁿ−αλ^n−j−(1−α)λ^n−k. In this paper, we prove that for any mn, if α1/2, then A^m+k−A^m_∞A^m−1w^T_∞, where 1 is the all-ones vector and w^T is the left-Perron vector for A, normalized so that w^T1=1. We also prove that if jn/2, n31 and , then A^m+j−A^m_∞A^m−1w^T_∞ for all sufficiently large m. Both of these results lead to lower bounds on the rate of convergence of the sequence A^m.     

Molecular orbital treatments of hydrogen bonded systems. 2. Dimers of water and HCN

Calculations were performed to investigate the reliabilities of the CNDO/2, PRDDO, and MNDO approximate molecular orbital methods. Systems selected for study included the linear, cyclic, and bifurcated dimers of water as well as the linear and cyclic dimers of HCN. The PRDDO method was found to provide the most consistently accurate reproduction of ab initio and experimental data. CNDO/2 performed fairly well in a number of cases but yielded extremely poor results for the cyclic dimers of both H₂O and HCN. Hydrogen bond strengths were consistently underestimated by MNDO which also furnished erroneously large intermolecular separations. In addition, MNDO calculations indicate the bifurcated water dimer to be most stable in contrast to other quantum mechanical and experimental information.See Ref. [1] for Paper 1 of this series.     

Shannon sampling II: Connections to learning theory

We continue our study [S. Smale, D.X. Zhou, Shannon sampling and function reconstruction from point values, Bull. Amer. Math. Soc. 41 (2004) 279–305] of Shannon sampling and function reconstruction. In this paper, the error analysis is improved. Then we show how our approach can be applied to learning theory: a functional analysis framework is presented; dimension independent probability estimates are given not only for the error in the L² spaces, but also for the error in the reproducing kernel Hilbert space where the learning algorithm is performed. Covering number arguments are replaced by estimates of integral operators.     

Hardy and BMO spaces associated to divergence form elliptic operators

Consider a second order divergence form elliptic operator L with complex bounded measurable coefficients. In general, operators based on L, such as the Riesz transform or square function, may lie beyond the scope of the Calderón–Zygmund theory. They need not be bounded in the classical Hardy, BMO and even some L ^p spaces. In this work we develop a theory of Hardy and BMO spaces associated to L, which includes, in particular, a molecular decomposition, maximal and square function characterizations, duality of Hardy and BMO spaces, and a John–Nirenberg inequality. S. Hofmann was supported by the National Science Foundation.     

Manifold Reconstruction in Arbitrary Dimensions Using Witness Complexes

It is a well-established fact that the witness complex is closely related to the restricted Delaunay triangulation in low dimensions. Specifically, it has been proved that the witness complex coincides with the restricted Delaunay triangulation on curves, and is still a subset of it on surfaces, under mild sampling conditions. In this paper, we prove that these results do not extend to higher-dimensional manifolds, even under strong sampling conditions such as uniform point density. On the positive side, we show how the sets of witnesses and landmarks can be enriched, so that the nice relations that exist between restricted Delaunay triangulation and witness complex hold on higher-dimensional manifolds as well. We derive from our structural results an algorithm that reconstructs manifolds of any arbitrary dimension or co-dimension at different scales. The algorithm combines a farthest-point refinement scheme with a vertex pumping strategy. It is very simple conceptually, and it does not require the input point sample to be sparse. Its running time is bounded by c(d)n ², where n is the size of the input point cloud, and c(d) is a constant depending solely (yet exponentially) on the dimension d of the ambient space. Although this running time makes our reconstruction algorithm rather theoretical, recent work has shown that a variant of our approach can be made tractable in arbitrary dimensions, by building upon the results of this paper. This work was done while S.Y. Oudot was a post-doctoral fellow at Stanford University. His email there is no longer valid.     

Equilibria of two-sided matching games with common preferences

Problems of matching have long been studied in the operations research literature (assignment problem, secretary problem, stable marriage problem). All of these consider a centralized mechanism whereby a single decision maker chooses a complete matching which optimizes some criterion. This paper analyzes a more realistic scenario in which members of the two groups (buyers–sellers, employers–workers, males–females) randomly meet each other in pairs (interviews, dates) over time and form couples if there is mutual agreement to do so. We assume members of each group have common preferences over members of the other group. Generalizing an earlier model of Alpern and Reyniers [Alpern, S., Reyniers, D.J., 2005. Strategic mating with common preferences. J. Theor. Biol. 237, 337–354], we assume that one group (called males) is r   times larger than the other, r?1$r?1$. Thus all females, but only 1/r$1/r$ of the males, end up matched. Unmatched males have negative utility -c$-c$. We analyze equilibria of this matching game, depending on the parameters r   and c$c$. In a region of (r,c)$(r\text{,}c)$ space with multiple equilibria, we compare these, and analyze their ‘efficiency’ in several respects. This analysis should prove useful for designers of matching mechanisms who have some control over the sex ratio (e.g. by capping numbers of males at a ‘singles event’or by having ‘ladies free’ nights) or the nonmating cost c (e.g. tax benefits to married couples).     

Modeling Language Evolution

We describe a model for the evolution of the languages used by the agents of a society. Our main result proves convergence of these languages to a common one under certain conditions. A few special cases are elaborated in more depth.     

Lattice path combinatorics and asymptotics of multiplicities of weights in tensor powers

We give asymptotic formulas for the multiplicities of weights and irreducible summands in high-tensor powers V_λ^⊗N of an irreducible representation V_λ of a compact connected Lie group G. The weights are allowed to depend on N, and we obtain several regimes of pointwise asymptotics, ranging from a central limit region to a large deviations region. We use a complex steepest descent method that applies to general asymptotic counting problems for lattice paths with steps in a convex polytope.     

A forest building process on simple graphs

Consider the following process on a simple graph without isolated vertices: order the edges randomly and keep an edge if and only if it contains a vertex which is not contained in some preceding edge. The resulting set of edges forms a spanning forest of the graph.The probability of obtaining $k$ components in this process for complete bipartite graphs is determined as well as a formula for the expected number of components in any graph. A generic recurrence and some additional basic properties are discussed.