Advertisement

In the past ** R.A. Cuninghame-Green** has collaborated on articles with

More information about

AbstractWe consider theories of linear and of polynomial algebra, over two scalar systems, often called max-algebra and min-algebra. Here, max-algebra is the system M = (R ∪ {−∞}, ⊛, ⊗) where x ⊛ y = max(x, y) and x ⊛ y = x + y. Min-algebra is the dual system M′ = R ∪ {+∞}, ⊛, ⊗′ with x ⊛′ y = min(x, y) and x ⊗′ y = x + y. Towards the end we also consider minimax algebra, the system M″ = (R ∪ {−∞, +∞}, ⊛, ⊗, ⊛′, ⊗′). Application fields discussed include location problems, machine scheduling, cutting and packing problems, discrete-event systems and path-finding problems.

AbstractPolynomial functions defined over the algebraic structure (R, max, + ) are discussed. All the basic algebraic processes of addition, multiplication, evolution and factorisation may be achieved by linear-time algorithms. Hence, given an equation of the form Ψ(x)=ΨPrime;(x) between two such polynomials, the extreme points of the solution set, and finally the full solution set, may be determined in linear time.

AbstractA piecewise-linear function whose definition involves the operator max and min may be reformulated as a ‘sum-of-partial-fractions’ by use of an algebraic structure J and so may be ‘rationalized’ to become a ‘quotient-of-polynomials’ in the notation of J We show that these ‘partial fractions’ and ‘polynomials’ have algebraic properties closely analogous to those of their counterparts in traditional elementary algebra: in particular an analogue of the fundamental theorem of algebra holds. These formal properties lead to straightforward procedures for finding maxima and minima of such functions.

AbstractWe present a formal long-division algorithm for solving the well-known group minimisation problem. In fact, given some group elements with associated positive costs, the algorithm produces a listing of all products of these elements, in ascending order of total cost. It may thus be applied to the solution of all-integer linear programs, by finding the cheapest solution to the group minimisation problem consistent with feasibility.

AbstractFor the algebraic structure (R, max, +) we study the continuous analogue of the eigenvector-eigenvalue problem and relate it to a minimal-cost orbit problem. An explicit solution is given for the concave-quadratic case.

AbstractAn interval system of equations is weakly solvable if at least one of its subsystems is solvable, and it is strongly solvable if all its subsystems are solvable. We give necessary and sufficient conditions enabling efficient testing of weak and strong solvability over max-plus and max-min algebras.

Publisher SummaryThis chapter discusses the applications of minimax algebra. The chapter discusses a discrete-event system (DES), in which the individual components move from event to event rather than varying continuously through time. A characteristic of many such DESs, which is focussed in the chapter, is that any given component must wait before proceeding to its next event until certain others have completed their current events. The chapter presents a hypothetical DES, containing four machines called the “model system.” Max algebra depends on a crucial change of notation. In place of the operator max, use of the symbol ⊕, reminiscent of an addition symbol instead of + use ⊗, reminiscent of a multiplication symbol. An AND-gate is a device used in signal processing. It is characterized by a single output and a number of inputs, each of which may be active or quiescent. A delay is characterized by a single input, a number of outputs, and a given fixed time-interval. The chapter discusses several processes of Max algebra, scheduling and approximation, Chebyshev approximation, and others.

AbstractWe discuss a method whereby the linear-system using standard max-algebraic techniques applied to a realization problem over max-algebra can be approached Hankel matrix. The method is computationally simpler than using a field-embedding.

Advertisement