Optimizing search with positive information feedback

A search model is formulated in which positive information may be obtained, through the detection of trails, as to the target's earlier whereabouts. The corresponding Bayesian update formulas for target location probabilities are derived. The model does not appear to be amenable to rigorous optimization. A moving-horizon rule, and a heuristic simplification thereof, are, however, derived. In two numerical examples it is demonstrated that actively designing for detecting trail information, through use of these moving-horizon rules, has substantial potential advantage over using, for example, myopic rules even if the positive information is adaptively incorporated into location probabilities before applying the latter rules in each time period.     

Rectilinear m-Center problem

In this article we consider the unweighted m-center problem with rectilinear distance. We preent an O(n^m–2 log n) algorithm for the m-center problem where m ≥ 4.     

Book reviews

Encyclopaedia of Modern Air Force Squadrons. By Chris Ashworth. Patrick Stephens, London (1989), ISBN 1-8526-013-6, £19.95

The Future of Sea Power. By Eric Grove. Routledge, London (1990), ISBN 0-415-00482-9, £35.00

Soviet Strategic Interests in the North. By Kirsten Amundsen. Pinter, London (1990), ISBN 0-86187-018-2, £30.00

Soviet Seapower in Northern Waters. Edited by John Skogan and Arne Brundtland. Pinter, London (1990), ISBN 0-86187-038-7, £35.00

Glasnost, Perestroika, and U.S. Defense Spending. By William W. Kaufmann, Brookings Institution, Washington, DC (1990), ISBN 0-8157-4881-7, $8.95

The Educating of Armies. Edited by Michael D. Stephens. Macmillan, London (1989), ISBN 0-333-43447-1, £35.00     

Minimizing the average deviation of job completion times about a common due date

This paper considers a single-machine scheduling problem in which penalities occur when a job is completed early or late. The objective is to minimize the total penalty subject to restrictive assumptions on the due dates and penalty functions for jobs. A procedure is presented for finding an optimal schedule.     

A linear programming approach to geometric programs

A cutting plane method, based on a geometric inequality, is described as a means of solving geometric programs. While the method is applied to the primal geometric program, it is shown to retain the geometric programming duality relationships. Several methods of generating the cutting planes are discussed and illustrated on some example problems.     

An algorithm for a class of loading problems

The loading problem we consinder is to assign a set of discrete objects, each having a weight, to a set of boxes, each of which has a capacity limit, in such a way that every object is assigned to a box and the number of boxes used is minimized. A characterization of the assignments is offered and used to develop a set of rules for generating nonredundant assignments. The rules are incorporated into an implicit enumeration algorithm. The algorithm is tested against a very good heuristic. Computational experience shows that the algorithm is highly efficient, solving problems of up to 3600 0-1 variables in a CPU second.     

Stochastic duels with bursts

In this analysis we extend the theory of stochastic duels to include the situation where one of the contestants fires a single infinitely long burst at a fixed rate of fire and secondly where he fires fixed-length, fixed-rate of fire bursts randomly spaced. In both cases the opponent fires single rounds randomly spaced. Special cases and parameter effects are considered.