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.     

Geometric programming with multiplicative slack variables

A posynomial geometric programming problem formulated so that the number of objective function terms is equal to the number of primal variables will have a zero degree of difficulty when augmented by multiplying each constraint term by a slack variable and including a surrogate constraint composed of the product of the slack variables, each raised to an undetermined negative exponent or surrogate multiplier. It is assumed that the original problem is canonical. The exponents in the constraint on the product of the slack variables must be estimated so that the associated solution to the augmented problem, obtained immediately, also solves the original problem. An iterative search procedure for finding the required exponents, thus solving the original problem, is described. The search procedure has proven quite efficient, often requiring only two or three iterations per degree of difficulty of the original problem. At each iteration the well-known procedure for solving a geometric programming problem with a zero degree of difficulty is used and so computations are simple. The solution generated at each iteration is optimal for a problem which differs from the original problem only in the values of some of the constraint coefficients, so intermediate solutions provide useful information.     

Heterogeneous discrete expenditure for diminishing returns

A probabilistic model is developed that applies to military bombardment, advertising for a mass audience, and other kinds of situations in which striking a target means that less of it is left to strike. The model provides the basis for decision analysis based on marginal gain in such circumstances. Heterogneous resources are considered as well as composite targets. All expenditures are quantized. The model has been developed as part of a computer-based military expert system, to replace a large complex set of expert opinions. In that application it sharply improves efficiency, yet conforms to major tenets of tactical doctrine.     

An analysis of constrained robust regression estimators

Multicollinearity and nonnormal errors are problems often encountered in the application of linear regression. Estimators are proposed for dealing with the simultaneous occurrence of both multicollinearity and nonnormality. These estimators are developed by combining biased estimation techniques with certain robust criteria. An iteratively reweighted least-squares procedure is used to compute the estimates. The performance of the combined estimators is studied empirically through Monte Carlo experiments structured according to factorial designs. With respect to a mean-squared-error criterion, the combined estimators are superior to ordinary least-squares, pure biased estimators, and pure robust estimators when multicollinearity and nonnormality are present. The loss in efficiency for the combined estimators relative to least squares is small when these problems do not occur. Some guidelines for the use of these combined estimators are given.     

Multiechelon repairable-item provisioning in a time-varying environment using the randomization technique

Multiechelon repairable-item provisioning systems are considered under a time-varying environment. Such conditions could arise, for example, in a military context where a shift from peacetime operation to wartime operation takes place; or, in a civilian setting where a public transit system decides to increase its hours of operation or frequency of service. Exact Markovian models, incorporating a finite population of repairable components and limited repair capacity (nonample service), are treated, with transient solutions obtained using the randomization technique. The exact models are compared with the approximate Dyna-METRIC model which assumes an infinite population of components and ample repair capacity.