zbMATH — the first resource for mathematics

An additive eigenvalue problem of physics related to linear programming. (English) Zbl 0639.65033
Starting from a functional equation for the ground state energy per atom by R. B. Griffiths a discrete approximation of this equation by \(\min_{j=1,...,n}(K_{ij}+x_ j)=\lambda +x_ i,\) \(i=1,...,n\) is investigated. Here \(K_{ij}\) is taken to be an arbitrary real square matrix. \(\lambda\) is termed an additive eigenvalue and x is termed an additive eigenvector. This additive eigenvalue equation had previously arisen in an entirely different area-management science. A motivation problem was cost efficient scheduling of industrial processes.
Brouwers fixed point theorem is used to show that a solution exists, that the eigenvalue is unique, but possibly there is more than one associated eigenvector. It is then shown that this equation can be solved by two linear programs. The first program has maximum value \(\lambda\). Then the second linear program furnishes a corresponding eigenvector.
Reviewer: J.Born

65K05 Numerical mathematical programming methods
90B35 Deterministic scheduling theory in operations research
90C08 Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.)
82B20 Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics
Full Text: DOI
[1] Griffiths, R.B; Chou, W, Effective potentials, a new approach and new results for one-dimensional systems with competing length scales, Phys. rev. lett., 56, 1929-1931, (1986)
[2] Chou, W; Griffiths, R.B, Ground states of one-dimensional systems using effective potentials, Phys. rev. B, 34, 6219-6234, (1986)
[3] Duffin, R.J, Finding Griffiths additive eigenvalues by linear programming, () · Zbl 0259.90032
[4] Aubry, S, J. phys. (Paris), 44, 147-157, (1983)
[5] Moser, J, Recent developments in the theory of Hamiltonian systems, SIAM rev., 28, 459-485, (1986) · Zbl 0606.58022
[6] Cuninghame-Green, R.A, Describing industrial processes with interference and approximating their steady-state behaviour, Oper. res. quart., 13, 95-100, (1962)
[7] Cuninghame-Green, R.A, Minimax algebra, (1979), Springer Berlin · Zbl 0399.90052
[8] Collatz, L, Functional analysis and numerical mathematics, (1966), Academic Press New York · Zbl 0221.65088
[9] Karp, R.M, A characterization of the minimum cycle Mean in a digraph, Discrete math., 23, 309-311, (1978) · Zbl 0386.05032
[10] Golitschek, M.V, Optimal cycles in doubly weighted graphs and approximation of bivariate functions by univariate ones, Numer. math., 39, 65-84, (1982) · Zbl 0541.65009
[11] Leizarowitz, A, Infinite horizon systems with unbounded costs, Appl. math. optim., 13, 19-43, (1985) · Zbl 0591.93039
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.