Herman Müntz: A Mathematician’s Odyssey

This column is a forum for discussion of mathematical communities throughout the world, and through all time. Our definition of ‘mathematical community’ is the broadest. We include ‘schools’ of mathematics, circles of correspondence, mathematical societies, student organizations, and informal communities of cardinality greater than one. What we say about the communities is just as unrestricted. We welcome contributions from mathematicians of all kinds and in all places, and also from scientists, historians, anthropologists, and others.     

Solving staircase linear programs by the simplex method, 2: Pricing

This and a companion paper consider how current implementations of the simplex method may be adapted to better solve linear programs that have a staged, or ‘staircase’, structure. The preceding paper considered ‘inversion’ routines that factorize the basis and solve linear systems. The present paper examines ‘pricing’ routines that compute reduced costs for nonbasic variables and that select a variable to enter the basis at each iteration. Both papers describe extensive (although preliminary) computer experiments, and can point to some quite promising results. For pricing in particular, staircase computation strategies appear to offer modest but consistent savings; staircase selection strategies, properly chosen, may offer substantial savings in number of iterations, time per iteration, or both.     

Instrumenting Mathematical Activity: Reflections on Key Studies of the Educational Use of Computer Algebra Systems

This paper examines the process through which students learn to make functional use of computer algebra systems (CAS), and the interaction between that process and the wider mathematical development of students. The result of ‘instrumentalising‘ a device to become a mathematical tool and correspondingly ‘instrumenting’ mathematical activity through use of that tool is not only to extend students' mathematical technique but to shape their sense of the mathematical entities involved. These ideas have been developed within a French programme of research – as reported by Artigue in this issue of the journal – which has explored the integration of CAS – typically in the form of symbolic calculators – into the everyday practice of mathematics classrooms. The French research –influenced by socio-psychological theorisation of the development of conceptual systems- seeks to take account of the cultural and cognitive facets of these issues, noting how mathematical norms – or their absence – shape the mental schemes which students form as they appropriate CAS as tools. Instrumenting graphic and symbolic reasoning through using CAS influences the range and form of the tasks and techniques experienced by students, and so the resources available for more explicit codification and theorisation of such reasoning. This illuminates an influential North American study– conducted by Heid – which French researchers have seen as taking a contrasting view of the part played by technical activity in developing conceptual understanding. Reconsidered from this perspective, it appears that while teaching approaches which ‘resequence skills and concepts’ indeed defer – and diminish –attention to routinised skills, the tasks introduced in their place depend on another –albeit less strongly codified – system of techniques, supporting more extensive and active theorisation. The French research high lights important challenges which arise in instrumenting classroom mathematical activity and correspondingly instrumentalising CAS. In particular, it reveals fundamental constraints on human-machine interaction which may limit the capacity of the present generation of CAS to scaffold the mathematical thinking and learning of students. This revised version was published online in July 2006 with corrections to the Cover Date.     

Roof duality,complementation and persistency in quadratic 0–1 optimization

The paper is concerned with the ‘primal’ problem of maximizing a given quadratic pseudo-boolean function. Four equivalent problems are discussed—the primal, the ‘complementation’, the ‘discrete Rhys LP’ and the ‘weighted stability problem of a SAM graph’. Each of them has a relaxation—the ‘roof dual’, the ‘quadratic complementation,’ the ‘continuous Rhys LP’ and the ‘fractional weighted stability problem of a SAM graph’. The main result is that the four gaps associated with the four relaxations are equal. Furthermore, a solution to any of these problems leads at once to solutions of the other three equivalent ones. The four relaxations can be solved in polynomial time by transforming them to a bipartite maximum flow problem. The optimal solutions of the ‘roof-dual’ define ‘best’ linear majorantsp(x) off, having the following persistency property: if theith coefficient inp is positive (negative) thenx _i=1 (0) in every optimum of the primal problem. Several characterizations are given for the case where these persistency results cannot be used to fix any variable of the primal. On the other hand, a class of gap-free functions (properly including the supermodular ones) is exhibited.     

Singularly perturbed and nonlocal modulation equations for systems with interacting instability mechanisms

Summary Two related systems of coupled modulation equations are studied and compared in this paper. The modulation equations are derived for a certain class of basic systems which are subject to two distinct, interacting, destabilising mechanisms. We assume that, near criticality, the ratio of the widths of the unstable wavenumber-intervals of the two (weakly) unstable modes is small—as, for instance, can be the case in double-layer convection. Based on these assumptions we first derive a singularly perturbed modulation equation and then a modulation equation with a nonlocal term. The reduction of the singularly perturbed system to the nonlocal system can be interpreted as a limit in which the width of the smallest unstable interval vanishes. We study and compare the behaviour of the stationary solutions of both systems. It is found that spatially periodic stationary solutions of the nonlocal system exist under the same conditions as spatially periodic stationary solutions of the singularly perturbed system. Moreover, these solutions can be interpreted as representing the same quasi-periodic patterns in the underlying basic system. Thus, the ‘Landau reduction’ to the nonlocal system has no significant influence on the stationary quasi-periodic patterns. However, a large variety of intricate heteroclinic and homoclinic connections is found for the singularly perturbed system. These orbits all correspond to so-called ‘localised structures’ in the underlying system: They connect simple periodic patterns atx → ± ∞. None of these patterns can be described by the nonlocal system. So, one may conclude that the reduction to the nonlocal system destroys a rich and important set of patterns.     

A changing trajectory of proof learning in the geometry inquiry classroom

The purpose of this study is to explore how students changes through learning to construct mathematical proofs in an inquiry-based middle school geometry class in Korea. Although proof has long been considered as one of the most important aspects of mathematics education, it is well-known that it is one of the most difficult areas of school mathematics for students. The geometry inquiry classroom (GIC) is an experimental class designed to teach geometry, especially focusing on teaching proof, based on students’ own inquiry. Based on a 2-year participant observation in the GIC, this study was conducted to address the following research question: how has students’ practice of mathematical proof been changed through their participation in the GIC? The in-depth analysis of the classroom discourse identified three stages through which the students’ practice of mathematical proof was transformed in the GIC: ‘emergent understanding of proof’, ‘proof learning as a goal-oriented activity’, ‘experiencing proof as the practice of mathematics’. The study found that as learning evolved through these stages, so the mathematics teacher’s role shifted from being an instructor to a mediator of communication. Most importantly, this research showed that the GIC has created a learning environment where students develop their competence in constructing meaningful mathematical proof and grow to be ‘a human who proves’, ultimately ‘a person who playfully engages with mathematics’.     

Adjustable robust optimization through multi-parametric programming

Adjustable robust optimization (ARO) involves recourse decisions (i.e. reactive actions after the realization of the uncertainty, ‘wait-and-see’     

Collapse of attractors for ODEs under small random perturbations

This paper concerns comparisons between attractors for random dynamical systems and their corresponding noiseless systems. It is shown that if a random dynamical system has negative time trajectories that are transient or explode with probability one, then the random attractor cannot contain any open set. The result applies to any Polish space and when applied to autonomous stochastic differential equations with additive noise requires only a mild dissipation of the drift. Additionally, following observations from numerical simulations in a previous paper, analytical results are presented proving that the random global attractors for a class of gradient-like stochastic differential equations consist of a single random point. Comparison with the noiseless system reveals that arbitrarily small non-degenerate additive white noise causes the deterministic global attractor, which may have non-zero dimension, to ‘collapse’. Unlike existing results of this type, no order preserving property is necessary.      

Imitation,coordination and the emergence of Nash equilibrium

We consider a learning dynamic in which players imitate and better reply. Sufficient conditions are provided for Nash equilibrium play to emerge over time. The role of imitation in the learning dynamic is discussed through a series of examples. Most interestingly we demonstrate how imitation can ‘help’ the emergence of Nash equilibrium where ‘more rational’ methods do not.     

Simulation based analysis of patient arrival to health care systems and evaluation of an operations improvement scheme

Various demands of different patients over both medical resource and time domains in health care systems raise requests of strategies for balanced system capacity from an operations perspective. In this paper, a quantitative modeling technique with both patient arrival and associated treatment process integrated are used to characterize health care system performance and evaluate system efficiency. The patient arrival process is described as a dynamic random Poisson process and patient treatments are characterized as consumption processes of various health care resources over time with a view of the “product line” used. The waiting time of patients and usage of health care resources are proposed as system performance measures based on their means, variances, and confidence intervals. A simulation considering patients with several various diseases is given to find a mechanism of conflicting factors in decisions of balanced system capacity, and an operation scheme of “evenly balanced load for bottlenecks” is obtained based on analysis of simulation outputs. Simul8 provides the software environment for the simulation.     

Smoothing algorithms for state–space models

Two-filter smoothing is a principled approach for performing optimal smoothing in non-linear non-Gaussian state–space models where the smoothing distributions are computed through the combination of ‘forward’ and ‘backward’ time filters. The ‘forward’ filter is the standard Bayesian filter but the ‘backward’ filter, generally referred to as the backward information filter, is not a probability measure on the space of the hidden Markov process. In cases where the backward information filter can be computed in closed form, this technical point is not important. However, for general state–space models where there is no closed form expression, this prohibits the use of flexible numerical techniques such as Sequential Monte Carlo (SMC) to approximate the two-filter smoothing formula. We propose here a generalised two-filter smoothing formula which only requires approximating probability distributions and applies to any state–space model, removing the need to make restrictive assumptions used in previous approaches to this problem. SMC algorithms are developed to implement this generalised recursion and we illustrate their performance on various problems.     

Potential,value, and coalition formation

In this paper, a simple probabilistic model of coalition formation provides a unified interpretation for several extensions of the Shapley value. Weighted Shapley values, semivalues, weak (weighted or not) semivalues, and the Shapley value itself appear as variations of this model. Moreover, some notions that have been introduced in the search of alternatives to Shapley’s seminal characterization, as ‘balanced contributions’ and the ‘potential’ are reinterpreted from this point of view. Natural relationships of these conditions with some mentioned families of ‘values’ are shown. These reinterpretations strongly suggest that these conditions are more naturally interpreted in terms of coalition formation than in terms of the classical notion of ‘value.’      

A semidefinite optimization approach to the steady-state analysis of queueing systems

Obtaining (tail) probabilities from a transform function is an important topic in queueing theory. To obtain these probabilities in discrete-time queueing systems, we have to invert probability generating functions, since most important distributions in discrete-time queueing systems can be determined in the form of probability generating functions. In this paper, we calculate the tail probabilities of two particular random variables in discrete-time priority queueing systems, by means of the dominant singularity approximation. We show that obtaining these tail probabilities can be a complex task, and that the obtained tail probabilities are not necessarily exponential (as in most ‘traditional’ queueing systems). Further, we show the impact and significance of the various system parameters on the type of tail behavior. Finally, we compare our approximation results with simulations.     

On the deformations of the incompressible Euler equations

We consider systems of deformed system of equations, which are obtained by some transformations from the system of incompressible Euler equations. These have similar properties to the original Euler equations including the scaling invariance. For one form of deformed system we prove that finite time blow-up actually occurs for ‘generic’ initial data, while for the other form of the deformed system we prove the global in time regularity for smooth initial data. Moreover, using the explicit functional relations between the solutions of those deformed systems and that of the original Euler system, we derive the condition of finite time blow-up of the Euler system in terms of solutions of one of its deformed systems. As another application of those relations we deduce a lower estimate of the possible blow-up time of the 3D Euler equations. This research was supported partially by the KOSEF Grant no. R01-2005-000-10077-0     

The <Emphasis Type="Italic">M</Emphasis>/<Emphasis Type="Italic">G</Emphasis>/∞ system revisited: finiteness,summability, long range dependence,and reverse engineering

We explore M/G/∞ systems ‘fed’ by Poissonian inflows with infinite arrival rates. Three processes – corresponding to the system's state, workload, and queue-size – are studied and analyzed. Closed form formulae characterizing the system's stationary structure and correlation structure are derived. And, the issues of queue finiteness, workload summability, and Long Range Dependence are investigated. We then turn to devise a ‘reverse engineering’ scheme for the design of the system's correlation structure. Namely: how to construct an M/G/∞ system with a pre-desired ‘target’ workload/queue auto-covariance function. The ‘reverse engineering’ scheme is applied to various examples, including ones with infinite queues and non-summable workloads. AMS Subject Classifications Primary: 60K25; Secondary: 60G55, 60G10     

Analysis and design of selection committees: a game theoretic secretary problem

Firms often delegate important decisions to committees which are set up specifically for that purpose; for example selection committees. We analyze the equilibrium behavior of a game in which committee members (the players) interview candidates sequentially, either hiring or going on to the next one. The players have differing evaluations of candidates (e.g. one cares about typing skills; the other about IT skills), which become their utilities if the candidate is hired. We then consider the optimal design (rules of the game) of such a committee, from the point of view of the firm. That is, which rules hire candidates which maximize the firm’s utility. Our committee game has a first round in which the members sequentially, by order of player number, say ‘yea’ or ‘nea’ to the candidate. If there are sufficient ‘yeas’ then she is tentatively hired; otherwise she is rejected. In the former case, members who said nea can veto the candidate in the second round. Thus the candidate is either hired, rejected, or vetoed. In the last case, the member casting a veto has one less to use on later candidates. We analyze equilibria where a player may say ‘yea’ to a candidate he would prefer not to hire, in order to force the other player to use up a valuable veto. We show that for the uniform candidate distribution there is a unique equilibrium and better candidates for the firm are hired when there are more vetoes. However we exhibit a candidate distribution where increasing the numbers of vetoes results in hiring worse candidates.     

Experiments with an interactive paired comparison simplex method for molp problems

In this paper, an interactive paired comparison simplex based method formultiple objective linear programming (MOLP) problems is developed and compared to other interactive MOLP methods. The decision maker (DM)’s utility function is assumed to be unknown, but is an additive function of his known linearized objective functions. A test for ‘utility efficiency’ for MOLP problems is developed to reduce the number of efficient extreme points generated and the number of questions posed to the DM. The notion of ‘strength of preference ’ is developed for the assessment of the DM’s unknown utility function where he can express his preference for a pair of extreme points as ‘strong ’, ‘weak ’, or ‘almost indifferent ’. The problem of ‘inconsistency of the DM’ is formalized and its resolution is discussed. An example of the method and detailed computational results comparing it with other interactive MOLP methods are presented. Several performance measures for comparative evaluations of interactive multiple objective programming methods are also discussed. All rights reserved. This study, or parts thereof, may not be reproduced in any form without written permission of the authors.     

Dynamic programming—neural network real-time traffic adaptive signal control algorithm

In this paper, an “intelligent” isolated intersection control system was developed. The developed “intelligent” system makes “real time” decisions as to whether to extend (and how much) current green time. The model developed is based on the combination of the dynamic programming and neural networks. Many tests show that the outcome (the extension of the green time) of the proposed neural network is nearly equal to the best solution. Practically negligible CPU times were achieved, and were thus absolutely acceptable for the “real time” application of the developed algorithm.     

Hamiltonian systems as selfdual equations

Hamiltonian systems with various time boundary conditions are formulated as absolute minima of newly devised non-negative action functionals obtained by a generalization of Bogomolnyi’s trick of ‘dcompleting squares’. Reminiscent of the selfdual Yang-Mills equations, they are not derived from the fact that they are critical points (i.e., from the corresponding Euler-Lagrange equations) but from being zeroes of the corresponding non-negative Lagrangians. A general method for resolving such variational problems is also described and applied to the construction of periodic solutions for Hamiltonian systems, but also to study certain Lagrangian intersections.