The square root of a sum of squares is well known to be prone to overflow and underflow. Ad hoc scaling of intermediate results, as has been done in numerical software such as the BLAS and LAPACK, mostly avoids the problem, but it can still occur at extreme values in the range of representable numbers. More careful scaling, as has been implemented in recent versions of the standard algorithms, may come at the expense of performance or clarity. This work reimplements the vector 2-norm and the generation of Givens rotations from the Level 1 BLAS to improve their performance and design. In addition, support for negative increments is extended to the Level 1 BLAS operations on a single vector, and a comprehensive test suite for all the Level 1 BLAS is included.

Wholesale electricity markets now operate in many countries around the world. These markets determine a spot price for electricity as the clearing price when generators bid in power at various prices. Because these markets are by nature repeated day after day, they are prone to tacit collusion between generators to raise prices. Tacit collusion occurs when a generator could improve its profits by changing its bid, but chooses not to do so because the long run result (as other generators also bid more aggressively) would be worse. A characteristic of such collusion is some type of punishment that occurs in the longer term if any player seeks a short-term advantage. It is hard to analyse such behaviour, partly because many possible (stable) collusive patterns exist. The approach taken here is to use a co-evolutionary genetic algorithm within a simple model of an electricity market to investigate the way that participants can learn collusive behaviour. We show that this framework does indeed lead to players adopting strategies of tacit collusion and we analyse the strategies that emerge. This also enables us to consider the ways in which the market environment increases or decreases the probability of collusion.

We consider rendezvous problems in which two players move on the plane and wish to cooperate in order to minimise their first meeting time. We begin by considering the case when they know that they are a distance d apart, but they do not know the direction in which they should travel. We also consider a situation in which player 1 knows the initial position of player 2, while player 2 is only given information on the initial distance of player 1. Finally we give some results for the case where one of the players is placed at an initial position chosen equiprobably from a finite set of points.

The CRAY T3E is a scalable shared-memory multiprocessor based on the DEC Alpha 21164 microprocessor. The system includes a number of novel architectural features designed to tolerate latency, enhance scalability, and deliver high performance on scientific and engineering codes. Included among these are stream buffers, which detect and prefetch down small-stride reference streams, E-registers, which provide latency hiding and non-unit-stride access capabilities, barrier and fetch_and_op synchronization support, and a scalable, high-bandwidth interconnection network.This paper reports our experiences with the CRAY T3E and presents a variety of performance measurements. Section 2 provides a brief overview of the system architecture. Section 3 describes the latency-hiding features (caches, stream buffers and E-registers) in more detail, assesses their performance impact, and discusses coding techniques for using them. Section 4 presents single-processor performance results. Finally, Section 5 discusses system scalability.

Genetic algorithms are one example of the use of a random element within an algorithm for combinatorial optimization. We consider the application of the genetic algorithm to a particular problem, the Assembly Line Balancing Problem. A general description of genetic algorithms is given, and their specialized use on our test-bed problems is discussed. We carry out extensive computational testing to find appropriate values for the various parameters associated with this genetic algorithm. These experiments underscore the importance of the correct choice of a scaling parameter and mutation rate to ensure the good performance of a genetic algorithm. We also describe a parallel implementation of the genetic algorithm and give some comparisons between the parallel and serial implementations. Both versions of the algorithm are shown to be effective in producing good solutions for problems of this type (with appropriately chosen parameters). INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

Abstract In this paper we discuss a search game on a network, Q , with two players, a searcher and a hider. The hider chooses a point on Q at which to hide, while the searcher starts at a given point on Q and moves with continuous trajectory subject to a maximal speed. This is a zero‐sum game with payoff given by the time elapsed until the searcher reaches the point occupied by the hider. The solution to this game is known for certain types of network. Here by formulating the problem as an infinite‐dimensional linear program, we derive an algorithm for its solution. We discuss the performance of the algorithm on three examples.

Abstract Given a network having costs and upper bound constraints on the flows in its arcs, the minimum‐cost network flow problem is that of finding flows which satisfy a flow‐conservation constraint at each node and minimize the total cost of the flow. If the arc capacities vary as functions of time, and storage is permitted at the nodes of the network, then the problem becomes an infinitedimensional linear program with a network structure. We describe an algorithm to solve such problems. This algorithm is a continuuous‐time version of the network simplex algorithm.

Abstract This paper discusses a class of search problems on networks, where the searcher only has information about that part of the network which he has traversed. These problems correspond to that of finding the exit of a maze. In this context it is natural to consider the two person game between the solver and the setter, where the setter may choose the maze subject to a constraint on the total length of its arcs. A particular strategy for the solver is investigated and shown to be optimal for this game.