Comparing Heegaard and JSJ structures of orientable 3-manifolds

The Heegaard genus of an irreducible closed orientable -manifold puts a limit on the number and complexity of the pieces that arise in the Jaco-Shalen-Johannson decomposition of the manifold by its canonical tori. For example, if of the complementary components are not Seifert fibered, then . This generalizes work of Kobayashi. The Heegaard genus also puts explicit bounds on the complexity of the Seifert pieces. For example, if the union of the Seifert pieces has base space and exceptional fibers, then .

     

The Inverse Problem of the Calculus of Variations for Sixth- and Eighth-order Scalar Ordinary Differential Equations

On the equation manifold of the 2nth-order scalar ordinary differential equation, n3,

Cane Railway Scheduling via Constraint Logic Programming: Labelling Order and Constraints in a Real-Life Application

In Australia, cane transport is the largest unit cost in the manufacturing of raw sugar, making up around 35% of the total manufacturing costs. Producing efficient schedules for the cane railways can result in significant cost savings. This paper presents a study using Constraint Logic Programming (CLP) to solve the cane transport scheduling problem. Tailored heuristic labelling order and constraints strategies are proposed and encouraging results of application to several test problems and one real-life case are presented. The preliminary results demonstrate that CLP can be used as an effective tool for solving the cane transport scheduling problem, with a potential decrease in development costs of the scheduling system. It can also be used as an efficient tool for rescheduling tasks which the existing cane transport scheduling system cannot perform well.     

The sdfem on Shishkin meshes for linear convection-diffusion problems

Summary. We consider singularly perturbed linear elliptic problems in two dimensions. The solutions of such problems typically exhibit layers and are difficult to solve numerically. The streamline diffusion finite element method (SDFEM) has been proved to produce accurate solutions away from any layers on uniform meshes, but fails to compute the boundary layers precisely. Our modified SDFEM is implemented with piecewise linear functions on a Shishkin mesh that resolves boundary layers, and we prove that it yields an accurate approximation of the solution both inside and outside these layers. The analysis is complicated by the severe nonuniformity of the mesh. We give local error estimates that hold true uniformly in the perturbation parameter , provided only that , where mesh points are used. Numerical experiments support these theoretical results. Received February 19, 1999 / Revised version received January 27, 2000 / Published online August 2, 2000     

Acoustic scattering in a rarefied gas: Solving the R13 equations in spherical polar coordinates

In some circumstances, sound waves in a rarefied gas can be studied using a linearised form of the regularised 13-moment equations of Struchtrup and Torrilhon. We build solutions of those equations in spherical polar coordinates using vector spherical harmonics. We first solve a reduced system of equations (with 11 unknowns) after introduction of a force vector (divergence of the stress). We then show that the stresses themselves can be recovered by solving five additional equations. The results obtained are expected to be useful for problems such as acoustic scattering of a plane wave by a sphere in a rarefied gas.     

Mixed integer linear models for the optimization of dynamical transport networks

We introduce a mixed integer linear modeling approach for the optimization of dynamic transport networks based on the piecewise linearization of nonlinear constraints and we show how to apply this method by two examples, transient gas and water supply network optimization. We state the mixed integer linear programs for both cases and provide numerical evidence for their suitability.     

Competitive evaluation of threshold functions in the priced information model

In Charikar et al. (J. Comput. Syst. Sci. 64(4):785–819, 2002) the authors proposed a new model for studying the function evaluation problem based on a variant of the classical decision tree problem for Boolean functions. In this variant each variable of the function to evaluate has an associated cost which has to be paid in order to read the value of the variable. Given a function f and an assignment σ to the variables of f, the performance of an algorithm for evaluating f is measured via the competitive ratio, i.e., the ratio of the total cost spent by the algorithm and the cost of the cheapest set of variables constituting a certificate for the value of the function on the given assignment.     

Finding the shortest paths by node combination

By repeatedly combining the source node’s nearest neighbor, we propose a node combination (NC) method to implement the Dijkstra’s algorithm. The NC algorithm finds the shortest paths with three simple iterative steps: find the nearest neighbor of the source node, combine that node with the source node, and modify the weights on edges that connect to the nearest neighbor. The NC algorithm is more comprehensible and convenient for programming as there is no need to maintain a set with the nodes’ distances. Experimental evaluations on various networks reveal that the NC algorithm is as efficient as Dijkstra’s algorithm. As the whole process of the NC algorithm can be implemented with vectors, we also show how to find the shortest paths on a weight matrix.     

A study of 3-arc graphs

An arc of a graph is an oriented edge and a 3-arc is a 4-tuple (v,u,x,y) of vertices such that both (v,u,x) and (u,x,y) are paths of length two. The 3-arc graph of a graph G is defined to have the arcs of G as vertices such that two arcs uv,xy are adjacent if and only if (v,u,x,y) is a 3-arc of G. In this paper, we study the independence, domination and chromatic numbers of 3-arc graphs and obtain sharp lower and upper bounds for them. We introduce a new notion of arc-coloring of a graph in studying vertex-colorings of 3-arc graphs.     

J.-H. Lambert’s theory of probable syllogisms

In his Neues Organon of 1764, the mathematician and astronomer Jean-Henri Lambert [12] developed a theory of probable syllogisms, with the aim of formally describing the probabilist reasoning and then applying it to the probability of testimony, thus imparting an epistemic sense to the concept of probability. In the present text, we propose to study the principles of this theory and the difficulties it raises.