Constructing greedy linear extensions by interchanging chains

A natural way to prove that a particular linear extension of an ordered set is ‘optimal’ with respect to the ‘jump number’ is to transform this linear extension ‘canonically’ into one that is ‘optimal’. We treat a ‘greedy chain interchange’ transformation which has applications to ordered sets for which each ‘greedy’ linear extension is ‘optimal’.     

Experimental analysis of heuristics for the bottleneck traveling salesman problem

In this paper we develop efficient heuristic algorithms to solve the bottleneck traveling salesman problem (BTSP). Results of extensive computational experiments are reported. Our heuristics produced optimal solutions for all the test problems considered from TSPLIB, JM-instances, National TSP instances, and VLSI TSP instances in very reasonable running time. We also conducted experiments with specially constructed ‘hard’ instances of the BTSP that produced optimal solutions for all but seven problems. Some fast construction heuristics are also discussed. Our algorithms could easily be modified to solve related problems such as the maximum scatter TSP and testing hamiltonicity of a graph.     

Convergence analysis of a conforming adaptive finite element method for an obstacle problem

The adaptive algorithm for the obstacle problem presented in this paper relies on the jump residual contributions of a standard explicit residual-based a posteriori error estimator. Each cycle of the adaptive loop consists of the steps ‘SOLVE’, ‘ESTIMATE’, ‘MARK’, and ‘REFINE’. The techniques from the unrestricted variational problem are modified for the convergence analysis to overcome the lack of Galerkin orthogonality. We establish R-linear convergence of the part of the energy above its minimal value, if there is appropriate control of the data oscillations. Surprisingly, the adaptive mesh-refinement algorithm is the same as in the unconstrained case of a linear PDE—in fact, there is no modification near the discrete free boundary necessary for R-linear convergence. The arguments are presented for a model obstacle problem with an affine obstacle χ and homogeneous Dirichlet boundary conditions. The proof of the discrete local efficiency is more involved than in the unconstrained case. Numerical results are given to illustrate the performance of the error estimator.     

Program Explanation and Higher-Order Properties

Our aim in this paper is to evaluate Frank Jackson and Philip Pettit’s ‘program explanation’ framework as an account of the autonomy of the special sciences. We argue that this framework can only explain the autonomy of a limited range of special science explanations. The reason for this limitation is that the framework overlooks a distinction between two kinds of properties, which we refer to as ‘higher-level’ and ‘higher-order’ properties. The program explanation framework can account for the autonomy of special science explanations that appeal to higher-level properties but it does not account for the autonomy of most of those explanations that appeal to higher-order properties.     

On The Span Of A Random Channel Assignment Problem

In the radio channel assignment problems considered here, we must assign a ‘channel’ from the set 1,2,... of positive integers to each of n transmitters, and we wish to minimise the span of channels used, subject to the assignment leading to an acceptable level of interference. A standard form of this problem is the ‘constraint matrix’ model. The simplest case of this model (the 0, 1 case) is essentially graph colouring. We consider here a random model for the next simplest case (with lengths 0, 1 or 2), and determine the asymptotic behaviour of the span of channels needed as n→∞. We find that there is a ‘phase change’ in this behaviour, depending on the probabilities for the different lengths.     

Moment inequalities and central limit properties of isotropic convex bodies

The object of our investigations are isotropic convex bodies , centred at the origin and normed to volume one, in arbitrary dimensions. We show that a certain subset of these bodies – specified by bounds on the second and fourth moments – is invariant under forming ‘expanded joinsrsquo;. Considering a body K as above as a probability space and taking , we define random variables on K. It is known that for subclasses of isotropic convex bodies satisfying a ‘concentration of mass property’, the distributions of these random variables are close to Gaussian distributions, for high dimensions n and ‘most’ directions . We show that this ‘central limit property’, which is known to hold with respect to convergence in law, is also true with respect to -convergence and -convergence of the corresponding densities. Received: 21 March 2001 / in final form: 17 October 2001 / Published online: 4 April 2002     

Artistic Expression Goes Green

The paper is a critical discussion of the rich and insightful final chapter of Mitchell Green’s Self-Expression. There, Green seeks to elucidate the compelling, but inchoate intuition that when we’re fully and most expertly expressing ourselves, we can ‘push out’ from within not just our inner representations, but also the ways that we feel. I question, first, whether this type of ‘qualitative expression’ is really distinct from the other expressive forms that Green explores, and also whether it’s genuinely ‘expressive’. I then scrutinize the nature of the ‘qualitative congruences’ that lie at the heart of Green’s theory; and I wonder whether they can play the role Green claims they can in providing a novel account of artistic expression.     

Self-regulation through social institutions: A framework for the design of open agent-based electronic marketplaces

In this paper, we argue that allowing self-interested agents to activate social institutions during runtime can improve the robustness (i.e., stability, reliability, or scalability) of open multiagent systems (MAS). Referring to sociological theory, we consider institutions to be rules that need to be activated and adopted by the agent population during runtime and propose a framework for self-regulation of MAS for the domain of electronic marketplaces. The framework consists of three different institutional types that are defined by the mechanisms and instances that generate, change or safeguard them. We suggest that allowing autonomous agents both the reasoning about their compliance with a rule and the selection of an adequate institutional types helps to balance the trade-off between the autonomy of self-interested agents and the maintenance of social order (cf. Castelfranchi, 2000) in MAS, and to ensure almost the same qualities as in closed environments. A preliminary report of the evaluation of the prototype by empirical simulations is given. Christian S. Hahn studied computer science and economics at Saarland University and received his diploma in 2004. Currently, he works in a project of the priority program ‘Socionics’ funded by the German Research Foundation at the German Research Center for Artificial Intelligence (DFKI). Bettina Fley studied sociology, economics, law, and social and economic history at the University of Hamburg and received her diploma in 2002. She currently works in a project in the priority program ‘Socionics’, which is funded by the German Research Foundation (DFG), at the Department of Technology Assessment at the Hamburg University of Technology. Michael Florian, received his master in sociology at the University of Münster, where he also finished his doctoral degree in 1993. Since 1995, he holds a position as a senior researcher (‘Oberingenieur’) at the Department of Technology Assessment at the Hamburg University of Technology and heads the sociological part of a project in the priority program ‘Socionics’ funded by the German Research Foundation (DFG).     

Quaternion Polar Representation with a Complex Modulus and Complex Argument Inspired by the Cayley-Dickson Form

We present a new polar representation of quaternions inspired by the Cayley-Dickson representation. In this new polar representation, a quaternion is represented by a pair of complex numbers as in the Cayley-Dickson form, but here these two complex numbers are a complex ‘modulus’ and a complex ‘argument’. As in the Cayley-Dickson form, the two complex numbers are in the same complex plane (using the same complex root of −1), but the complex phase is multiplied by a different complex root of −1 in the exponential function. We show how to calculate the ‘modulus’ and ‘argument’ from an arbitrary quaternion in Cartesian form.     

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.     

Error-free transformations of matrix multiplication by using fast routines of matrix multiplication and its applications

This paper is concerned with accurate matrix multiplication in floating-point arithmetic. Recently, an accurate summation algorithm was developed by Rump et al. (SIAM J Sci Comput 31(1):189–224, 2008). The key technique of their method is a fast error-free splitting of floating-point numbers. Using this technique, we first develop an error-free transformation of a product of two floating-point matrices into a sum of floating-point matrices. Next, we partially apply this error-free transformation and develop an algorithm which aims to output an accurate approximation of the matrix product. In addition, an a priori error estimate is given. It is a characteristic of the proposed method that in terms of computation as well as in terms of memory consumption, the dominant part of our algorithm is constituted by ordinary floating-point matrix multiplications. The routine for matrix multiplication is highly optimized using BLAS, so that our algorithms show a good computational performance. Although our algorithms require a significant amount of working memory, they are significantly faster than ‘gemmx’ in XBLAS when all sizes of matrices are large enough to realize nearly peak performance of ‘gemm’. Numerical examples illustrate the efficiency of the proposed method.     

Extending the Ehresmann-Schein-Nambooripad Theorem

We extend the ‘∨-premorphisms’ part of the Ehresmann-Schein-Nambooripad Theorem to the case of two-sided restriction semigroups and inductive categories, following on from a result of Lawson (J. Algebra 141:422–462, 1991) for the ‘morphisms’ part. However, it is so-called ‘∧-premorphisms’ which have proved useful in recent years in the study of partial actions. We therefore obtain an Ehresmann-Schein-Nambooripad-type theorem for (ordered) ∧-premorphisms in the case of two-sided restriction semigroups and inductive categories. As a corollary, we obtain such a theorem in the inverse case.     

Moore’s Paradox,Truth and Accuracy

G. E. Moore famously observed that to assert ‘I went to the pictures last Tuesday but I do not believe that I did’ would be ‘absurd’. Moore calls it a ‘paradox’ that this absurdity persists despite the fact that what I say about myself might be true. Krista Lawlor and John Perry have proposed an explanation of the absurdity that confines itself to semantic notions while eschewing pragmatic ones. We argue that this explanation faces four objections. We give a better explanation of the absurdity both in assertion and in belief that avoids our four objections.     

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.     

On the syntactic algorithm for the word problem of left distributivity

Here we investigate the ‘natural’ syntactic algorithm for the word problem of left distributivity, and we establish a sufficient condition which explains the convergence for all terms of a reasonable size. An algorithm for left division is also constructed. Received February 8, 1996; accepted in final form October 3, 1996     

Universal properties of stable states of a free energy model with small parameters

We consider the problem of minimizing functionals of the form , for small , subject to the constraint . (Here is typically a double well potential.) We study structural properties of minimizers that are shared by all minimizers of the problem, for sufficiently small values of . It is shown that the average ‘mass’ and ‘energy’ of minimizers, over intervals of length , is almost uniformly distributed (depending on ), for all sufficiently small . Here is a constant depending on the degree of ‘uniformity’, but independent of . Received May 5, 1996 / Accepted October 28, 1996     

On Estimating a Dynamic Function of a Stochastic System with Averaging

We consider a two-scaled diffusion system, when drift and diffusion parameters of the ‘slow’ component are contaminated by the ‘fast’ unobserved component. The goal is to estimate the dynamic function which is defined by averaging the drift coefficient of the ‘slow’ component w.r.t. the stationary distribution of the ‘fast’ one. We apply a locally linear smoother with a data-driven bandwidth choice. The procedure is fully adaptive and nearly optimal up to a log log factor. This revised version was published online in June 2006 with corrections to the Cover Date.     

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.’      

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.