bluuebunny/crossref_metadata_2025_split huggingface dataset:
Survival and effectiveness of a weapon system against a superior force (guerrilla warfare)
Authors: Bache N. 
Published: May 2007

AbstractStochastic models are developed for a weapon system which attacks at a certain rate, but withdraws when attacked (guerrilla warfare). The models yield as output the distributions and mean values in closed form of the survival period and number of attacks made. As input are, for the weapon system, attack rate or amount of ammunition and time horizon, and, for the opponent, kill rate and probability of killing the weapon system, given the opponent has been attacked (strike back performance of the opponent). One model allows, however, for strike back also by the weapon system, when attacked by the opponent. This model is then used to determine, when the weapon system should strike back. The models are based on the Poisson and the binomial processes. Consistency among the models is shown and an example is provided.
Modified discrete preventive maintenance policies
Authors: Nakagawa Toshio 
Published: May 2007

AbstractThis article proposes a modified preventive maintenance (PM) policy which may be done only at scheduled times nT (n = 1,2, …): The PM is done at the next such time if and only if the total number of failures exceeds a specified number k. The optimal number k* to minimize the expected cost rate is discussed. Further, four alternative similar PM models are considered, when the system fails due to a certain number of faults, uses, shocks, and unit failures.
Rescheduling to minimize makespan on a changing number of identical processors
Authors: Tovey Craig A. 
Published: May 2007

AbstractWe consider the problem of rescheduling n jobs to minimize the makespan on m parallel identical processors when m changes value. We show this problem to be NP‐hard in general. Call a list schedule totally optimal if it is optimal for all m = 1, …,n. When n is less than 6, there always exists a totally optimal schedule, but for n ≥ 6 this can fail. We show that an exact solution is less robust than the largest processing time first (LPT) heuristic and discuss implications for polynomial approximation schemes and hierarchical planning models.
Algorithms for the minimax transportation problem
Authors: Ahuja R. K. 
Published: May 2007

AbstractIn this paper, we consider a variant of the classical transportation problem as well as of the bottleneck transportation problem, which we call the minimax transportation problem. The problem considered is to determine a feasible flow xij from a set of origins I to a set of destinations J for which max(i,j)εIxJ{cijxij} is minimum. In this paper, we develop a parametric algorithm and a primal‐dual algorithm to solve this problem. The parametric algorithm solves a transportation problem with parametric upper bounds and the primal‐dual algorithm solves a sequence of related maximum flow problems. The primal‐dual algorithm is shown to be polynomially bounded. Numerical investigations with both the algorithms are described in detail. The primal‐dual algorithm is found to be computationally superior to the parametric algorithm and it can solve problems up to 1000 origins, 1000 destinations and 10,000 arcs in less than 1 minute on a DEC 10 computer system. The optimum solution of the minimax transportation problem may be noninteger. We also suggest a polynomial algorithm to convert this solution into an integer optimum solution.
Optimal replacement for fault‐tolerant systems
Authors: Taylor Howard M. , Rodriguez Beatriz E. 
Published: May 2007

AbstractWe consider the optimal replacement problem for a fault tolerant system comprised of N components. The components are distingushable, and the state of the system is given by knowing exactly which components are operationl and which have failed. The individual component failure rates depend on the state of the entire system. We assume that the rate at which the system produces income decreases as the system deteriorates and the system replacement cost rises. Individual components cannot be replaced. We give a greedy‐type algorithm that produces the replacement policy that maximizes the long‐run net system income per unit time.
Optimal refueling sequence for a mixed fleet with limited refuelings
Authors: Melkman Avraham A. , Stern Helman I. , Mehrez Avraham 
Published: May 2007

AbstractConsider a fleet of vehicles comprised of K1 identical tankers and K2 identical nontankers (small aircraft). Tankers are capable of refueling other tankers as well as nontankers. The problem is to find that refueling sequence of the tankers that maximizes the range simultaneously attainable by all K2 nontankers. A recent paper established that the “unit refueling sequence,” comprised of one tanker refueling at each of K1 refueling operations, is optimal. The same paper also proffered the following conjecture for the case that the number of refueling operations is constrained to be less than the number of tankers: A nonincreasing refueling sequence is optimal. This article proves the conjecture.
Estimating the accuracy of the coverages of outer β‐content tolerance intervals, which control both tails of the normal distribution
Authors: Chou Youn‐Min , Owen D. B. 
Published: May 2007

AbstractTolerance limits which control both tails of the normal distribution so that there is no more than a proportion β1 in one tail and no more than β2 in the other tail with probability γ may be computed for any size sample. They are computed from X̄ ‐ k1S and X̄ ‐ k2S, where X̄ and S are the usual sample mean and standard deviation and k1 and k2 are constants previously tabulated in Odeh and Owen [3]. The question addressed is, “Just how accurate are the coverages of these intervals (– Infin;, X̄ – k1S) and (X̄ + k2S, ∞) for various size samples?” The question is answered in terms of how widely the coverage of each tail interval differs from the corresponding required content with a given confidence γ′.
A study of the analysis and control of the flow of air traffic: Part I
Authors: Forys L. J. , Heffes H. , Holtzman J. M. , Horing S. , Messerli E. J. , Schwartz M. I. , Stiles J. A. 
Published: May 2007

AbstractThis paper contains the results of an exploratory study aimed at developing a model which could form the basis of a comprehensive analysis of the Air Traffic Control system. This model could be used to evaluate the effects of proposed changes in the system.The results will be presented in three parts. Part I is intended to provide an overview of the results as well as a detailed description of a traffic flow model which computes the means and variances of delays experienced by individual aircraft. Since this model requires as an input a statistical description of the arrival and departure service processes, Part II describes a model which relates these processes to more basic quantities (e.g., aircraft mix, runway configuration). Since the models which are developed represent a physical system, the question of validation arises and is also discussed in Part II. Part III of the paper considers the question of designing a (real‐time) flow control system. It is formulated as a problem of minimizing a measure of system delay subject to constraints on the allowable departure and arrival times. Illustrative results are included through‐out the paper.
A decomposition approach to nonlinear programs as applied to reservoir systems
Authors: Bodin L. D. , Roefs T. G. 
Published: May 2007

AbstractThe problem considered in this paper is the determination of the operating policy over time of a network of water reservoirs or dams arranged according to an arbitrary topology. If streamflow was a known quantity, the problem could be formulated as a large nonlinear program (several hundred nonlinear) constraints as a minimum) and solved by the two methods proposed in this paper. Since streamflow is random, the problem becomes a large stochastic program which can be solved by a procedure given in the literature. The key step in solving this stochastic program is the solution of the nonlinear program by the methods we propose.
A study of the analysis and control of the flow of air traffic: Part III
Authors: Forys L. J. , Heffes H. , Holtzman J. M. , Horing S. , Messerli E. J. , Schwartz M. I. , Stiles J. A. 
Published: May 2007

AbstractThis is the third and final part of a study of the analysis and control of the flow of air traffic. Part I developed a traffic flow model to compute the means and variances of delays experienced by individual aircraft. Part II was concerned with the arrival and departure processes, and with the question of model validation. In this part, we consider an approach to the problem of designing a (real‐time) flow control system. Central to the approach is the problem of minimizing a measure of system delay subject to constraints on the allowable departure and arrival times.
Optimal flow in networks with gains and costs
Authors: Malek‐Zavarei M. , Aggarwal J. K. 
Published: May 2007

AbstractThe problem of routing a desired flow at minimum cost through a network in which associated with each arc is a capacity, a linear cost, a fixed cost and a flow multiplier is considered. The equivalence of the problems on a general graph and a bipartite graph is shown; feasibility is discussed and properties of solutions are investigated.
An optimal schedule time of a job shop‐like disjunctive graph
Authors: Ashour S. , Chiu K. Y. , Moore T. E. 
Published: May 2007

AbstractThis paper considers the shop scheduling problem which involves both job precedence and machine interference constraints. Based on the graph‐theoretical representation of the problem, a branch‐and‐bound algorithm is proposed for implicitly producing an optimal schedule such that the schedule time is minimized. The algorithm utilizes a set of heuristic rules, in addition to a powerful bounding procedure, to guide the search. An upper bound is also employed to recognize an optimal solution in earlier stages. The procedure is illustrated by a sample problem and its rapid convergence is demonstrated by a set of published problems. The proposed algorithm is compared favorably with existing procedures.
Routing a fleet of M vehicles to/from a central facility
Authors: Orloff C. S. 
Published: May 2007

AbstractIn a previous paper, algorithms for optimally routing a single vehicle were presented. In this paper, the problem of routing a fleet of M vehicles serving fixed demand for transportation from many origins to a single destination is considered. The M vehicle General Routing Problem (abbreviated M‐GRP) is the core of many real routing problems, such as school bus routing for a single school (many‐to‐one) and garbage truck routing to a central dump. It is shown that the M‐GRP on a given graph is equivalent to a GRP on a modified graph. From this result, it is shown that single vehicle routing algorithms can be applied to the M vehicle routing problem.
Shortest path with time constraints on movement and parking
Authors: Halpern J. , Priess I. 
Published: May 2007

AbstractThe shortest path problem is well known and a number of methods have been proposed for its solution. In its simplest form no restrictions or special costs are placed on movement in the network. Some variations of the problem have been presented and solved, such as requirements for visiting specified nodes, turn penalties and prohibitions and time‐dependent length of arcs. In this paper we present and solve the case where we seek the shortest path when some arcs are closed for travelling during specified periods of time. We allow parking in the vertices of the network, when it is necessary to wait for an arc to be opened, but we also assume the possibility of “no‐parking” or “occupied” periods in the nodes. This type of problem emerges, for example, in the management of railway system, or a network of narrow roads with convoys moving on it.
On clique‐extremal (p,q)‐graphs
Authors: Harary F. , Lempel A. 
Published: May 2007

AbstractA clique of a graph is a maximal complete subgraph. A (p,q)‐graph has p points and q lines. A clique‐extremal (p,q)‐graph has either the maximum or the minimum number of cliques among all (p,q)‐graphs. Moon and Moser have determined constructively the maximum number of cliques in a p‐point graph. The problem of studying the clique‐extremal (p,q)‐graphs is now investigated. We first develop a standard form for such extremal graphs. These standard forms are shown to have a complementary kind of analogy with respect to maximum and minimum.
A minimum‐cost multicommodity network flow problem concerning imports and exports
Authors: Golden B. L. 
Published: May 2007

AbstractThis paper develops an algorithm for handling nonlinear minimum‐cost multicommodity flow problems and applies it to a specific large‐scale network. The commodities will be imports and exports; the cost functions will be quadratic and convex. The setting will be a Port Planning Model which will seek to find optimal simultaneous routings through the network while fulfilling requirements both at foreign ports and at domestic hinterlands. The computer program written solves such a problem. The algorithm involves linearizing the cost function and solving the resulting linear program, which is, in fact, a series of shortest route problems. Negative cycles are studied in depth.
An algebra for determining all path‐values in a network with application to K‐shortest‐paths problems
Authors: Wongseelashote A. 
Published: May 2007

AbstractThis paper presents an algebra which is appropriate for the formulation and solution of k‐Shortest‐paths problems. The algebra is a generalization of “Schedule Algebra” studied by Giffler [3,4] for computing path values in a network. It is shown formally that these path values can be calculated by using direct methods of numerical linear algebra for solving systems of linear equations and an algorithm similar to the long division procedure of ordinary arithmetic. Such a method is then modified to yield an algorithm for finding k shortest elementary paths in a network.
Minimal ratio spanning trees
Authors: Chandrasekaran R. 
Published: May 2007

AbstractGiven an undirected graph G: (N;E) with a node set N and an edge set E and numbers Ce and De, e ϵ E, we provide a polynominally bounded algorithm to solve the problem: Find a spanning tree T such that the ratio magnified image is minimized. An extension to finding bases in matroids that minimize such ratio functions is immediate. It is shown that an algorithm that is “greedy,” in the sense of Edmonds [2], will not work for this problem.
Bounding distributions for a stochastic pert network
Authors: Shogan A. W. 
Published: May 2007

AbstractConsider a PERT network with stochastic activity durations. This paper presents a new method for obtaining probability distributions that bound the exact probability distribution of the project duration from above and below. The expected values of these bounding distributions then furnish lower and upper bounds on the expected project duration. As illustrated by computational experience, these bounds are tighter than those obtained from methods currently in use. The paper concludes by describing similar results for stochastic shortest‐route networks.
A decomposition algorithm for network reliability analysis
Authors: Shogan A. W. 
Published: May 2007

AbstractConsider a directed, source‐sink network whose arcs either function or fail with known probabilities. This paper presents a decomposition algorithm for the exact computation of the reliability of such a network; that is, the probability that there exists a path from the network's source to its sink, consisting only of functioning arcs. The decomposition algorithm, which can be used even after the network can undergo no further modular decomposition, is based on a partitioning of the nodes of the network into subsets that can be sequentially analyzed. The algorithm permits arbitrary dependence among arcs that terminate at nodes belonging to the same subset of the partition but requires two arcs terminating at nodes belonging to different subsets to be independent. Computational experience from a computer implementation of the algorithm is also reported.
A generalized dynamic flows problem
Authors: Halpern J. 
Published: May 2007

AbstractThe original maximal dynamic flows problem is to find the maximal flow that may be transferred within a given period of time, from the source to the destination of a network with constant edge capacities and lengths. This paper generalizes the problem in two ways. First, the edge's capacity is time dependent, and secondly, the heldover of flows in the vertices may be prohibited during certain intervals of time. The presence of these two additional features implies that cycling of flows may be necessary in order to generate an optimal solution, an impossible result in the original problem. The generalized maximal dynamic flows problem requires, therefore, a special method of solution, and the paper presents a suitable algorithm which solves the problem.
Realization of a symmetric terminal capacity matrix by a tree with the minimum diameter
Authors: Ozawa T. 
Published: May 2007

AbstractTrees realizing a terminal capacity matrix (TCM) have a unique layer structure. An algorithm making use of this layer structure is presented for construction of a tree which realizes the TCM with the smallest possible diameter. This minimum‐diameter tree has layers of stars. An upper bound on the minimum diameter is given for a prescribed number of vertices. Also presented are algorithms to construct a star and a tree of diameter 3 which realize the TCM as a minimum requirement matrix.
A more compact formulation of the symmetric multiple traveling salesman problem with fixed charges
Authors: Discenza Joseph Henry 
Published: May 2007

AbstractThe multiple traveling salesman problem with fixed charges (MTSPF) is an extension of the standard traveling salesman problem (TSP). Previous work by Hong and Padberg showed how to transform to a TSP with n + m + 4 nodes, where m is the number of salesmen. The four extra nodes were included to prevent the transformed problem from escaping part of the fixed costs. This paper shows that two of these nodes can be eliminated without sacrificing the formulation as a TSP. Further, all four extra nodes can be replaced by a pair of simple constraints. All formulations produce equivalent solutions.
Combinatorial optimization and vehicle fleet planning: Perspectives and prospects
Authors: Magnanti T. L. 
Published: May 2007

AbstractAs a well‐structured and costly activity that pervades industries in both the public and private sector, vehicle fleet management would appear to be a splendid candidate for model‐based planning and optimization. And yet, until recently the combinatorial intricacies of vehicle routing and of vehicle scheduling have precluded the widespread use of optimization (exact) methods for this problem class. Our discussion in this paper identifies the extent and nature of these problem complexities and draws contrasts with other applications of combinatorial optimization. It also summarizes a number of successful uses of optimization for vehicle fleet planning and highlights potentially fruitful avenues for algorithmic development. In particular, we describe several alternative models and novel algorithms for the vehicle routing problem, show how various modeling approaches for this problem are intimately related, and illustrate the interplay between model formulations and the algorithms that they suggest. This discussion shows that prospects for applying exact methods, possibly in conjunction with heuristics, are far from fully realized and points to vehicle fleet planning as a tempting target of opportunity for further investigation.
Finding a minimum equivalent graph of a digraph
Authors: Martello Silvano , Toth Paolo 
Published: May 2007

AbstractThe problem considered is that of removing the maximum number of edges from a digraph without affecting its reachability properties. The worst‐case performance of algorithms from the related literature is analyzed; it is found that Hsu's method contains some mistakes. A new algorithm is presented, based on a reduction procedure and on a branch and bound search; its efficiency is studied both theoretically and through computational experiments.
Maximum flow in networks with a small number of random arc capacities
Authors: Somers J. E. 
Published: May 2007

AbstractIn a directed, capacitated network with single source and sink in which the capacities of some of the arcs are random variables, the max‐flow value is also a random variable. I propose a new approach to the problem of computing its distribution and expected value via a corollary of the max‐flow min‐cut theorem, and implement it explicitly for small numbers of random capacities. I consider the error obtained in estimating the expected max‐flow value by setting some of the random capacities equal to their means. When the flows are restructed by lower bounds, I give the probability of existence of a feasible flow.
On‐line connectivity algorithms
Authors: Cheston Grant A. 
Published: May 2007

AbstractThe problem is to be able to respond to inquiries of the form “Are vertices u and v of graph G connected?” as quickly as possible in an on‐line situation where edges are being inserted into and deleted from the graph. Recently Even and Shiloach presented a data structure and algorithm involving three synchronized processes to handle the deletion case. An alternative algorithm, LEVELS, is presented to update their data structure. This algorithm is more efficient than theirs and has the further feature of not requiring synchronized processes, so that it is much easier to implement. Finally the LEVELS algorithm is compared to and contrasted with an algorithm using a spanning‐forest data structure for both edge insertion and deletion. The LEVELS algorithm appears to be better for deletion, while the spanning‐forest algorithm is better for insertion.
Mesh association by projection along smoothed‐normal‐vector fields: Association of closed manifolds
Authors: van Brummelen E. H. 
Published: May 2007

AbstractThe necessity to associate two geometrically distinct meshes arises in many engineering applications. Current mesh‐association algorithms have generally been developed for piecewise‐linear geometry approximations, and their extension to the high‐order geometry representations corresponding to high‐order finite element methods is nontrivial. In the present work, we therefore propose a mesh‐association method for high‐order geometry representations. The associative map defines the image of a point on a mesh as its projection along a so‐called smoothed‐normal‐vector field onto the other mesh. The smoothed‐normal‐vector field is defined by the solution of a modified Helmholtz equation with right‐hand‐side data corresponding to the normal‐vector field. Classical regularity theory conveys that the smoothed‐normal‐vector field is continuously differentiable, which renders it well suited for a projection‐based association. Moreover, the regularity of the smoothed‐normal‐vector field increases with the regularity of the normal‐vector field and, hence, the smoothness of the association increases with the smoothness of the geometry representations. The proposed association method thus accommodates the higher regularity that can be provided by high‐order geometry representations. Several important properties of smoothed‐normal‐projection association are established by analysis and by numerical experiments on closed manifolds. Copyright © 2007 John Wiley & Sons, Ltd.