On finding spanning eulerian subgraphs

In this article, we examine the problem of producing a spanning Eulerian subgraph in an undirected graph. After the ?-completeness of the general problem is established, we present polynomial-time algorithms for both the maximization and minimization versions where instances are defined on a restricted class of graphs referred to as series-parallel. Some novelties in the minimization case are discussed, as are heuristic ideas.     

Interception in a network

This paper presents an algorithm for determining where to place intercepting units in order to maximize the probability of preventing an opposing force from proceeding from one particular node in an undirected network to another. The usual gaming assumptions are invoked; namely, the strategy for placing the units is known to the opponent and he will choose a path through the network which, based on this knowledge, maximizes his probability of successful traverse. As given quantities, the model requires a list of the arcs and nodes of the network, the number of intercepting units available to stop the opposing force, and the probabilities for stopping the opposition at the arcs and nodes as functions of the number of intercepting units placed there. From these quantities, the algorithm calculates the probabilities for placing the unit at the arcs and nodes when one intercepting unit is available, and the expected numbers of units to place at the arcs and nodes when multiple intercepting units are available.     

Cumulative search-evasion games

Cumulative search-evasion games (CSEGs) are two-person zero-sum search-evasion games where play proceeds throughout some specified period without interim feedback to either of the two players. Each player moves according to a preselected plan. If (X_t, Y_t,) are the positions of the two players at time t, then the game's payoff is the sum over t from 1 to T of A(X_t, Y_t, t). Additionally, all paths must be “connected.” That is, the finite set of positions available for a player in any time period depends on the position selected by that player in the previous time period. One player attempts to select a mixed strategy over the feasible T-time period paths to maximize the expected payoff. The other minimizes. Two solution procedures are given. One uses the Brown-Robinson method of fictitious play and the other linear programming. An example problem is solved using both procedures.     

Estimation and prediction in a semi-markov model for evasive vehicle movement along a fixed path

In Turner and Holmes [8] a model for evasive vehicle movement along a fixed track is developed within the mathematical framework of a two-state semi-Markov process. They derive a number of analytical properties of the model. In this article we address problems concerning the estimation of parameters in the model and the construction of data-based prediction equations.     

Assessment of hazardous-inspection policies

Inspection procedures may at times pose a hazard to the system being monitored. In this article, a simple hazardous-inspection model is considered. The character of the optimal ongoing inspection policy (for inspections subsequent to the first) is reviewed, and the possible forms of the optimal initiation policy are established. Efficient computational procedures are developed for calculating optimal policies. Some discussion is included of the counterintuitive nature of some of the results.     

Location of facilities with rectangular distances among point and area destinations

This article is concerned with the optimal location of any number (n) of facilities in relation to any number (m) of destinations on the Euclidean plane. The criterion to be satisfied is the minimization of total weighted distances where the distances are rectangular. The destinations may be either single points, lines or rectangular areas. A gradient reduction solution procedure is described which has the property that the direction of descent is determined by the geometrical properties of the problem.     

Stochastic duels involving reliability

The reliability of weapons in combat has been treated by Bhashyam in the context of a stochastic duel characterized by fixed ammunition supplies. negative exponentially distributed firing times and weapon lifetimes, and a fixed number of spare weapons for each duelist. The present paper takes a different approach by starting with the fundamental duel of Ancker and Williams, characterized by unlimited ammunition and by ordinary renewal firing times, and adding to it weapon lifetimes which can be functions of time or of round position in the firing sequence. Probabilities of winning and tieing are derived and it is shown that under certain conditions the weapon lifetimes are equivalent to random time and ammunition limits.     

An optimum t-test for the scale parameter of an extreme-value distribution

A Student's t-test proposed by Ogawa is considered for the hypothesis Ho: σ=σo against the alternative hypothesis H₁: σ ≠ σo, where σ is the scale parameter of the Extremevalue distribution of smallest values with known location parameter μ. The test is based on a few sample quantiles chosen from a large sample so as to give asymptotically maximum power to the test when the number of sample quantiles is fixed. A table which facilitates the computation of the test statistic is given. Several schemes for determining the ranks of the sample quantiles by the optimal spacings are compared and the effect of the bias of the estimate of σ on the test is investigated through a Monte Carlo study.