bluuebunny/crossref_metadata_2025 huggingface dataset:
State Dependent Expected Utility for Savage's State Space
Authors: Wakker Peter P. , Zank Horst
Published: October 2008

This paper generalizes the Debreu/Gorman characterization of additively decomposable functionals and separable preferences to infinite dimensions. The first novelty concerns the very definition of additively decomposable functionals for infinite dimensions. For decision under uncertainty, our result provides a state-dependent extension of Savage's expected utility. A characterization in terms of preference conditions identifies the empirical content of the model; it amounts to Savage's axiom system with P4 (likelihood ordering) dropped. Our approach does not require that a (probability) measure on the state space be given a priori, or can be derived from extraneous conditions outside the realm of decision theory. Bayesian updating of new information is still possible, even though no prior probabilities are given. The finding suggests that the sure-thing principle, rather than prior probability, is at the heart of Bayesian updating.
Lifted Cycle Inequalities for the Asymmetric Traveling Salesman Problem
Authors: Balas Egon , Fischetti Matteo
Published: October 2008

We investigate the family of facet defining inequalities for the asymmetric traveling salesman (ATS) polytope obtainable by lifting the cycle inequalities. We establish several properties of this family that earmark it as arguably the most important among the asymmetric inequalities for the ATS polytope known to date. In particular, we give several results that characterize the pattern of lifting coefficients and thereby facilitate the identification of facet defining inequalities. This characterization is used to investigate three new, large classes of lifted cycle inequalities that we call shell, fork and curtain inequalities. These latter inequalities have unbounded Chvátal rank. Furthermore, the pattern of lifting coefficients that we identify makes it easy to develop efficient separation routines. Finally, each member of the family is shown to have a counterpart for the symmetric TS (STS) polytope that is often new, and is obtainable by mapping the inequality for the ATS polytope into a certain face of the STS polytope and then lifting the resulting inequality into one for the STS polytope itself.
The Complexity of Optimal Queuing Network Control
Authors: Papadimitriou Christos H. , Tsitsiklis John N.
Published: October 2008

We show that several well-known optimization problems related to the optimal control of queues are provably intractable—independently of any unproven conjecture such as P ≠ NP. In particular, we show that several versions of the problem of optimally controlling a simple network of queues with simple arrival and service distributions and multiple customer classes is complete for exponential time. This is perhaps the first such intractability result for a well-known optimization problem. We also show that the restless bandit problem (the generalization of the multi-armed bandit problem to the case in which the unselected processes are not quiescent) is complete for polynomial space.
Optimization of Multiclass Queueing Networks with Changeover Times Via the Achievable Region Approach: Part I, The Single-Station Case
Authors: Bertsimas Dimitris , Niño-Mora José
Published: October 2008

We address the performance optimization problem in a single-station multiclass queueing network with changeover times by means of the achievable region approach. This approach seeks to obtain performance bounds and scheduling policies from the solution of a mathematical program over a relaxation of the system's performance region. Relaxed formulations (including linear, convex, nonconvex and positive semidefinite constraints) of this region are developed by formulating equilibrium relations satisfied by the system, with the help of Palm calculus. Our contributions include: (1) new constraints formulating equilibrium relations on server dynamics; (2) a flow conservation interpretation of the constraints previously derived by the potential function method; (3) new positive semidefinite constraints; (4) new work decomposition laws for single-station multiclass queueing networks, which yield new convex constraints; (5) a unified buffer occupancy method of performance analysis obtained from the constraints; (6) heuristic scheduling policies from the solution of the relaxations.
Optimization of Multiclass Queueing Networks with Changeover Times Via the Achievable Region Approach: Part II, The Multi-Station Case
Authors: Bertsimas Dimitris , Niño-Mora José
Published: October 2008

We address the problem of scheduling a multi-station multiclass queueing network (MQNET) with server changeover times to minimize steady-state mean job holding costs. We present new lower bounds on the best achievable cost that emerge as the values of mathematical programming problems (linear, semidefinite, and convex) over relaxed formulations of the system's achievable performance region. The constraints on achievable performance defining these formulations are obtained by formulating system's equilibrium relations. Our contributions include: (1) a flow conservation interpretation and closed formulae for the constraints previously derived by the potential function method; (2) new work decomposition laws for MQNETs; (3) new constraints (linear, convex, and semidefinite) on the performance region of first and second moments of queue lengths for MQNETs; (4) a fast bound for a MQNET with N customer classes computed in N steps; (5) two heuristic scheduling policies: a priority-index policy, and a policy extracted from the solution of a linear programming relaxation.
Stochastic Convexity on General Space
Authors: Meester Ludolf E. , Shanthikumar J. George
Published: October 2008

This paper presents a general theory of stochastic convexity. The notions of stochastic convexity formulated by Shaked and Shanthikumar (1988a, 1988b, 1990) are defined for general partially ordered spaces. All of the closure properties of the one-dimensional real theory are proved to be true in this general framework as well and results concerning the temporal convexity of Markov chains are sharpened. Many proofs are based on new ideas, some of which also provide insightful alternatives for proofs in Shaked and Shanthikumar (1990).

The general theory encompasses the (largely one-dimensional) stochastic convexity theory as known from these papers, and at the same time permits treatment of multivariate multiparameter families as well as more general random objects. Among others, it applies to real vector spaces and yields a theory of stochastic convexity for random vectors and stochastic processes.

We illustrate this new scope with examples and applications from queueing theory, coverage processes, reliability and branching processes. We show that the virtual waiting time process of an NHPP driven ·/G/1 queue is stochastically convex in the arrival intensity function, which explains the known adverse effect of fluctuating arrival rates; that the expected size of an i.i.d. union of random sets grows concavely; that the expected utility of repairable items under imperfect repair policies is increasing and convex in the probabilities of successful repair.
Martingale Measures and Hedging for Discrete-Time Financial Markets
Authors: Schäl Manfred
Published: October 2008

The price of stocks is modelled by a discrete-time, square-integrable, vector-valued process X. No further boundedness condition on X is imposed. Contingent claims H are described by square-integrable random variables. One looks for values v of the initial wealth v that allow for super-hedging H by some portfolio plan. In several cases, the smallest value v is known to coincide with the maximal expectation of H under equivalent martingale measures. Here, within an L 2-framework, another sufficient condition is provided which can be looked upon as a stronger form of the no-arbitrage condition. The mathematical tool and one of the main contributions is an optional decomposition theorem for a process which is a supermartingale under any equivalent martingale measure. The upper price process for a contingent claim is shown to be a typical example for such a process. Moreover it is shown that in a Markovian model one can restrict attention to Markovian portfolio plans and to Markovian martingale measures.
Three-Player Absorbing Games
Authors: Solan Eilon
Published: October 2008

An n-player absorbing game is an n-player stochastic game where all the states but one are absorbing (a state is absorbing if once it is reached, the probability to leave it is zero, whatever the players play).

We prove that every three-player absorbing game has an undiscounted equilibrium payoff.
Mean Cost Cyclical Games
Authors: Pisaruk N. N.
Published: October 2008

We study the mean cost cyclical game in a more general setting than that in Gurvitch et al. (1988) and Karzanow and Lebedev (1993). The game is played on a directed graph and generalizes the single source shortest path problem, the minimum mean cycle problem (see Karp 1978), and the ergodic extension of matrix games (Moulin 1976). We prove the existence of a solution in uniform stationary strategies and present an algorithm for finding such optimal strategies. In fact, our algorithm is an extension of the algorithms due to Gurvitch et al. (1988) and Karzanow and Lebedev (1993), which were proved to be finite, but exponential in the worst case. We prove that all these algorithms are pseudopolynomial.
Ill-Conditioned Convex Processes and Conic Linear Systems
Authors: Lewis A. S.
Published: October 2008

We prove the smallest possible norm of a linear perturbation making a closed convex process nonsurjective is the inverse of the norm of the inverse process. This generalizes the fundamental property of the condition number of a linear map. We then apply this result to strengthen a theorem of Renegar measuring the size of perturbation necessary to make a conic linear system inconsistent.
Stochastic Orderings of Convex/Concave-Type on an Arbitrary Grid
Authors: Denuit Michel , Lefèvre Claude , Utev Sergey
Published: October 2008

Several new classes of discrete stochastic orderings are introduced for comparing discrete random variables that are valued in an arbitrary ordered finite grid of nonnegative points. These order relations correspond to particular cases of integral stochastic orderings which are generated by different classes of functions of convex/concave-type defined on the grid. They are natural extensions from equidistant to arbitrary grids of various orderings familiar in the literature. The main question addressed in the paper is how an extension of the grid of points can affect such stochastic orderings. It will be shown that a crucial factor is the location of the additional point that is inserted in the grid.
Minimizing Total Completion Time in a Two-Machine Flowshop: Analysis of Special Cases
Authors: Hoogeveen J. A. , Kawaguchi T.
Published: October 2008

We consider the problem of minimizing total completion time in a two-machine flowshop. We present a heuristic with worst-case bound 2β/(α + β), where α and β denote the minimum and maximum processing time of all operations. Furthermore, we analyze four special cases: equal processing times on the first machine, equal processing times on the second machine, processing a job on the first machine takes time no less than its processing on the second machine, and processing a job on the first machine takes time no more than its processing on the second machine. We prove that the first special case is NP-hard in the strong sense and present an O(n log n) approximation algorithm for it with worst-case bound 4/3. We repeat the easy polynomial algorithms for the cases two and three, and show that problem four is solvable in polynomial time as well.
Erratum: A Sharp Upper Bound for the Expected Number of Shadow Vertices in LP-Polyhedra Under Orthogonal Projection on Two-Dimensional Planes
Authors: Borgwardt Karl Heinz
Published: October 2008

Due to an error in typesetting, an incorrect version of Figure 1 was printed as part of this paper in Mathematics of Operations Research, Vol. 24 No. 3, August 1999, pp. 544–603 . The paper is reprinted correctly here.
A Generalization of Erlang's Loss System to State Dependent Arrival and Service Rates
Authors: Brumelle Shelby L.
Published: October 2008

An Erlang Loss System with state dependent arrival and service rates is examined. This model includes Processor Shared Systems and birth-death processes. The state of the system is the number of occupied servers, the time until the next arrival, and the amounts of work remaining for the customers being served. Stationary probability distributions and conditions for their existence are determined for the continuous time process observed at arrivals and departures. The average delay of a customer is also computed.
Optimal Inspections in a Stochastic Control Problem with Costly Observations, II
Authors: Anderson Robert F. , Friedman Avner
Published: October 2008

A Brownian motion ξ(t) is developing in time with cost f(ξ(t)) per unit time. It is assumed that ξ(t) = (x(t), y(t)) where x(t) and y(t) are independent Brownian motions. The component x(t) is being continuously observed, whereas the position of y(t) can be discovered only by making observations at random times σn with incurred cost β(ξ(σn)). Thus, σn is a stopping time with respect to the σ-field generated by x(t), t ≥ 0 and the random variables y(σ1), …, y(σn−1). A set A is given, and at the time σn the following policy is executed: (a) continue with the process until the next inspection, if y(σn) ∈ A, (b) stop and shut off the process with cost γ(ξ(σn) if y(σn) ∉ A. The problem considered in this paper is that of finding an optimal sequence of inspections {σn} This is done by first transforming the stochastic problem into a free boundary problem in analysis and then studying the latter.
Optimal Allocations of Continuous Resources to Several Activities with a Concave Return Function—Some Theoretical Results
Authors: Einbu J. M.
Published: October 2008

The problem of allocating J continuous resources to K competing activities each with a concave return function is considered. The following results pertaining to the space of optimal solution to this problem are proved:

—under the most unrestricted conditions an optimal solution is almost always unique;

—there exists at least one optimal solution with J + K − 1 or less allocations;

—there exists at least one optimal solution for which the number of activities having multiple allocations is at most J − 1;

Also, sufficient input conditions for a unique optimal solution are established and it is shown how the dimension and extent of the optimal solution space can be derived directly from the output matrix.
Discovering Hidden Totally Leontief Substitution Systems
Authors: Dantzig George B. , Veinott Arthur F.
Published: October 2008

A constructive procedure is given for determining the existence of and evaluating (when it does exist) a nonsingular matrix that transforms a system of linear equations in nonnegative variables into a totally Leontief substitution system. The computational effort involved is about that required to optimize the given m-row linear system with m + 1 different linear objective functions.
On Stochastic Games with Stationary Optimal Strategies
Authors: Bewley Truman , Kohlberg Elon
Published: October 2008

We study two-person zero-sum stochastic games in which the state and action spaces are finite. We give both necessary and sufficient conditions for the players to have stationary optimal strategies in the infinite-stage game.
Properties of the Process of Level Crossings During a Busy Cycle of the M/G/1 Queueing System
Authors: Cohen J. W.
Published: October 2008

The variables d(v), v ∈ (0, ∞) with d(v) the number of downcrossings of level v of the virtual waiting time process during a busy cycle of a queueing system constitute a stochastic process {d(v), v > 0}. For a stable M/G/1 queueing system this process is investigated in the present paper. Under certain conditions on the density of the service time distribution it is shown that this process is a birth and death process with constant birth rate and time-dependent death rate; however, for the M/M/1 system this process {d(v), v > 0} has also constant death rate. A number of properties of the d(v)-process are studied, yielding also some new results for the M/G/1 queueing system. In particular an explicit expression is found for the variance of the area underneath the sample function of the virtual waiting time process during a busy cycle, thus solving a question posed by Iglehart.
An Asymptotic, Probabilistic Analysis of a Routing Problem
Authors: Stein David M.
Published: October 2008

Certain “Bus Problems” are defined as generalizations of the traveling salesman problem. The simplest result concerns the length of the tour required by a single bus to pick up and deliver n passengers from random locations to random destinations in a bounded region of the plane. It is shown that the length of the tour divided by the square root of n converges almost surely to the square root of slightly more than twice the area of the region as n goes to infinity. When several buses are available, the length of the tour is simply divided by the number of buses. The bus problems have been motivated by the practical problem of scheduling dial-a-ride transportation systems.
Best Algorithms for Approximating the Maximum of a Submodular Set Function
Authors: Nemhauser G. L. , Wolsey L. A.
Published: October 2008

A real-valued function z whose domain is all of the subsets of N = {1, …, n) is said to be submodular if z(S) + z(T) ≥ z(S ∪ T) + z(S ∩ T), ∀S, T ⊆ N, and nondecreasing if z(S) ≤ z(T), ∀S ⊂ T ⊆ N. We consider the problem maxS⊂N {z(S): |S| ≤ K, z submodular and nondecreasing, z(Ø) = 0}.

Many combinatorial optimization problems can be posed in this framework. For example, a well-known location problem and the maximization of certain boolean polynomials are in this class.

We present a family of algorithms that involve the partial enumeration of all sets of cardinality q and then a greedy selection of the remaining elements, q = 0, …, K − 1. For fixed K, the qth member of this family requires O(nq+1) computations and is guaranteed to achieve at least [Formula: see text] Our main result is that this is the best performance guarantee that can be obtained by any algorithm whose number of computations does not exceed O(nq+1).
Computational Complexity of the Game Theory Approach to Cost Allocation for a Tree
Authors: Megiddo Nimrod
Published: October 2008

In the game theory approach to the problem of allocating cost, the users of a facility are viewed as players in a cooperative n-person game. It is the nature of cooperative games that the power of each one of the 2n−1 possible coalitions is taken into account. Thus, practical problems of allocating cost may be intractable in the game theory approach because of the computational complexity involved. However, it is shown that good algorithms do exist for the nucleolus and the Shapley value allocations for a tree. The nucleolus can be computed within O(n3) operations and the Shapley allocation in O(n) operations.
The Hirsch Conjecture Fails for Triangulated 27-Spheres
Authors: Walkup David W.
Published: October 2008

A triangulation Z of a 27-sphere is generated in which every sequence of adjacent 27-simplices joining a specified pair of disjoint 27-simplices revisits at least one vertex previously left behind. This shows thai the Hirsch conjecture, which asserts the existence of a nonredundant feasible pivot sequence between any pair of bases of a linear program, or equivalently a nonrevisiting sequence of facets of a simplicial polytope, is false when generalized in the obvious way to triangulated spheres. The complex Z is constructed from a complex with 400 4-simplices which has been shown to be shellable, and hence a 4-ball, by a computer computation.
The Functional Equations of Undiscounted Markov Renewal Programming
Authors: Schweitzer P. J. , Federgruen A.
Published: October 2008

This paper investigates the solutions to the functional equations that arise inter alia in Undiscounted Markov Renewal Programming. We show that the solution set is a connected, though possibily nonconvex set whose members are unique up to n* constants, characterize n* and show that some of these n* degrees of freedom are locally rather than globally independent.

Our results generalize those obtained in Romanovsky (Romanovsky, I. 1973. On the solvability of Bellman's functional equation for a Markovian decision process. J. Math. Anal. Appl. 42 485–498.) where another approach is followed for a special class of discrete time Markov Decision Processes. Basically our methods involve the set of randomized policies. We first study the sets of pure and randomized maximal-gain policies, as well as the set of states that are recurrent under some maximal-gain policy.
An Axiomatic Theory of Tournament Aggregation
Authors: Monjardet B.
Published: October 2008

An axiomatic theory for aggregation of individual preferences is developed. Many authors, since K. J. Arrow, have studied the case where every individual preference is an ordering. We study here the case where every individual preference is a tournament (for instance, in “paired comparisons”). The original results obtained can be compared to those of the classic theory. For example, we prove, in this context, a generalisation of Arrow's theorem and we emphasize duality between Arrow's results and Black-Inada-Sen's results (technically by means of a Galois connection between two lattices). We used social functions defined by means of “families of majorities” (simple games),
Determining All Solutions to Certain Systems of Nonlinear Equations
Authors: Garcia C. B. , Zangwill W. I.
Published: October 2008

Only during the past decade has it been discovered how, under fairly reasonable conditions, to calculate a solution of a system of n nonlinear equations in n variables. The technique utilized was the so-called “complementarity” or “fixed point” approach to the Brouwer fixed point theorem. In this paper we extend that approach to calculate for certain systems not just one but all possible solutions. All solutions can be calculated when the equations of the system behave like a polynomial in the highest order terms. That is, in each equation the highest order term must be a variable raised to a power while the lower order terms can be more general.

Our procedure starts with a trivial system of equations, one to which all solutions are obvious and immedately known. The trivial system is then deformed into the system given with the unknown solutions. The idea is to follow the paths generated from the obvious solutions into the unknown solutions of the given system. This process under rather general conditions calculates all of the solutions.
Universally Measurable Policies in Dynamic Programming
Authors: Shreve Steven E. , Bertsekas Dimitri P.
Published: October 2008

Powerful dynamic programming results concerning existence and characterizations of optimal or nearly optimal policies, convergence of algorithms and characterizations of the optimal cost function have been available for some time (see Bellman [Bellman, R. 1957. Dynamic Programming. Princeton University Press, Princeton, NJ.]), but a rigorous proof of these results has required quite restrictive hypotheses, such as countability of the state space, in order to circumvent the inherent measurability difficulties. Some of these results or weaker versions of them have been proved by Blackwell (Blackwell, D. 1965. Positive dynamic programming. Proc. Fifth Berkeley Symposium on Math. Stat. and Prob. 415–418; Blackwell, D. 1965. Discounted dynamic programming. Ann. Math. Stat. 36 226–235.), Strauch (Strauch, R. E. 1966. Negative dynamic programming. Ann. Math. Stat. 37 871–890.), Hinderer (Hinderer, K. 1970. Foundations of Nonstationary Dynamic Programming with Discrete Time Parameter. Springer, New York.), Dynkin and Juskevic (Dynkin, E. B., A. A. Juskevic. 1975. Controlled Markov Processes and Their Applications. Moscow. English translation to be published by Springer.) and others in the framework of Borel spaces and Borel measurable policies. We show that the use of universally measurable policies in the Borel space framework resolves the measurability issues so that all the basic results of dynamic programming can be obtained in the strongest possible form. In particular, ϵ-optimal policies are shown to exist, the dynamic programming algorithm is defined and conditions and bounds for its convergence to the optimal cost are given. The optimality equation is shown to hold and is used to characterize the optimal cost function and optimal policies.
Quotatone Apportionment Methods
Authors: Balinski M. L. , Young H. P.
Published: October 2008

The problem of apportionment is that of allocating an integer number of seats “proportionally” among a set of states or regions as a fraction of their populations. An apportionment method satisfies quota if it accords to each state the exactly proportional (rational) number of seats due it rounded up or rounded down. A method is house monotone if no state’s allocation goes down when the total number of seats to be distributed goes up.

This paper gives a simple characterization of all house monotone methods satisfying quota. Further, a manner of exposition is formulated which unites several key house monotone apportionment methods, thus showing clearly their connections.
A Strongly Convergent Primal Simplex Algorithm for Generalized Networks
Authors: Elam Joyce , Glover Fred , Klingman Darwin
Published: October 2008

A major computational problem that arises in the attempt to solve generalized network and network-related problems is degeneracy. In fact, using primal simplex solution techniques, the number of degenerate pivots performed frequently ranges as high as 90% in large-scale applications. The purpose of this paper is to develop a special set of structural and logical relationships for generalized network problems with positive “gains” that yields a new primal simplex algorithm which exploits degeneracy. The major mathematical differences between this new algorithm and the original simplex method are (1) each basis examined is restricted to have a special topology, (2) the algorithm is finitely convergent without reliance upon “external” techniques such as lexicography or perturbation, and (3) a special screening criterion for nondegenerate basis exchanges is available that allows some of these exchanges to be recognized prior to finding the representation of an incoming arc.
On the Convergence of Policy Iteration in Stationary Dynamic Programming
Authors: Puterman Martin L. , Brumelle Shelby L.
Published: October 2008

The policy iteration method of dynamic programming is studied in an abstract setting. It is shown to be equivalent to the Newton-Kantorovich iteration procedure applied to the functional equation of dynamic programming. This equivalence is used to obtain the rate of convergence and error bounds for the sequence of values generated by policy iteration. These results are discussed in the context of the finite state Markovian decision problem with compact action space. An example is analyzed in detail.
Tangent Cones, Generalized Gradients and Mathematical Programming in Banach Spaces
Authors: Hiriart-Urruty J. B.
Published: October 2008

This study is devoted to constrained optimization problems in Banach spaces. We present different properties of tangent cones associated with an arbitrary subset of a Banach space and establish correlations with some of the existing results. In absence of both differentiability and convexity assumptions on the functions involved in the optimization problem, the consideration of these tangent cones and their polars leads us to introduce new concepts in nondifferentiable programming. Necessary optimality conditions are first developed in a general abstract form; then these conditions are made more precise in the presence of equality constraints by introducing the concept of normal subcone.
Matroids and a Reliability Analysis Problem
Authors: Ball Michael O. , Nemhauser George L.
Published: October 2008

We present an algorithm for the reliability analysis problem of determining the probability that a stochastic binary system operates. The stochastic binary system is viewed as an independence system. The algorithm finds a partition of the set of independence sets into subsets called intervals. If F ⊆ G, the interval between F and G is the collection of subsets F with F ⊆ F′ ⊆ G. The probability of an event corresponding to an interval is easy to calculate and the probability that the system operates is simply the sum of the event probabilities corresponding to the intervals in the partition.

For any independence system a lower bound on the number of intervals needed in a partition is the number of bases. We show that for matroids this bound can be attained. Our algorithm finds a minimum cardinality interval partition of a matroid and characterizes matroids.
Theoretical Properties of the Network Simplex Method
Authors: Cunningham W. H.
Published: October 2008

An example of cycling in the network simplex method is given and some restrictions on its occurrence are proved. An example of “stalling” (an exponentially long sequence of consecutive degenerate pivots without cycling) is also given, and two methods which prevent cycling are shown to admit stalling. Pivoting rules which prevent the occurrence of both cycling and stalling are described, and some computational advantages are noted. Related results for the upper-bounded and dual simplex methods are also described.
Computing Economic Equilibria on Affine Networks with Lemke's Algorithm
Authors: Asmuth Richard , Eaves B. Curtis , Peterson Elmor L.
Published: October 2008

Consider a multicommodity transhipment problem where the prices at each location are an affine function of the supplies and demands at that location and the shipping costs are an affine function of the quantities shipped. A system of prices, supplies, demands, and shipments is defined to be an equilibrium, if there is a balance in the shipments, supplies, and demands of goods at each location, if local prices do not exceed the cost of importing, and if shipments are price efficient. Lemke’s algorithm is used to compute an equilibrium.
Sequencing with Series-Parallel Precedence Constraints
Authors: Monma Clyde L. , Sidney Jeffrey B.
Published: October 2008

One of the most important ideas in the theory of sequencing and scheduling is the method of adjacent pairwise job interchange. This method compares the costs of two sequences which differ only by interchanging a pair of adjacent jobs. In 1956, W. E. Smith defined a class of problems for which a total preference ordering of the jobs exists with the property that in any sequence, whenever two adjacent jobs are not in preference order, they may be interchanged with no resultant cost increase. In such a case the unconstrained sequencing problem is easily solved by sequencing the jobs in preference order.

In this paper, a natural subclass of these problems is considered for which such a total preference ordering exists for all subsequences of jobs. The main result is an efficient general algorithm for these sequencing problems with series-parallel precedence constraints. These problems include the least cost fault detection problem, the one-machine total weighted completion time problem, the two-machine maximum completion time flow-shop problem and the maximum cumulative cost problem.
Simplified Characterizations of Linear Complementarity Problems Solvable as Linear Programs
Authors: Mangasarian O. L.
Published: October 2008

New and simplified characterizations are given for solving, as a linear program, the linear complementarity problem of finding an x in Rn such that Mx + q ≥ 0, x ≥ 0 and x1(Mx + q) = 0. The simplest such characterization given here is that if there exist n-dimensional vectors c, r, s which are nonnegative, and n-by-n matrices Z1, Z2, with nonpositive off-diagonal elements such that (i) MZ1 = Z2 + qcT and (ii) rTZ1 + sTZ2 > 0, then each solution of the linear program: Minimizex (rT + sT M)x subject to Mx + q ≥ 0, x ≥ 0, solves the linear complementarity problem. Conversely, if the linear complementarity problem has at least one vertex solution x which is nondegenerate. that is, x + Mx + q > 0, then there exist nonnegative vectors c, r, s and matrices Z1, Z2, with nonpositive off-diagonal elements, such that (i)–(ii) are satisfied.
Minimal Forbidden Subgraphs of Unimodular Multicommodity Networks
Authors: Truemper K. , Soun Y.
Published: October 2008

An integral matrix with independent columns is called unimodular if the greatest common divisor of the determinants of its maximum-rank square submatrices is one. An integral matrix A (not necessarily having independent columns) is defined to be unimodular if every basis of A has that property. It is known that this is so if and only if the extreme points of the set of nonnegative vectors x satisfying Ax = b are integral for all integral vectors b. Here the constraint matrix of a k-commodity network flow problem is shown to be unimodular if and only if the associated (undirected) graph does not have a subgraph homeomorphic to the following graphs: (i) the complete graph on four nodes, and if k ≥ 3, (ii) a cycle with three additional edges, each a duplicate of a different edge of the cycle, having no node with degree 2 (these graphs have from three to six nodes).

The following algorithm checks whether subgraphs of the above type are present. First find the 2-connected subgraphs that contain at least two edges. Then reduce each such subgraph to a graph with fewer nodes and arcs. The forbidden subgraphs are not present if and only if the algorithm reduces each 2-connected subgraph to a cycle with two edges. When this is not possible, a forbidden subgraph is produced. Suitable implementation of the algorithm results in O(n) complexity, where n is the number of edges of the original graph.
Almost Sure Comparisons of Renewal Processes and Poisson Processes, with Application to Reliability Theory
Authors: Miller Douglas R.
Published: October 2008

If the interarrival times of a renewal process {Si, i = 0, 1, 2…} have a failure rate function which is bounded away from 0 and ∞, then it is possible to construct (nonhomogeneous) Poisson processes {Ti0, i = 0, 1, 2, …} and {Ti1, i = 0, 1, 2, …} on the same probability space with {Si, i = 0, 1, 2, …} such that {T00, T10, T20, …} ⊂ {S0, S1, S2, …} ⊂ {T01, T11, T21, …} almost surely. This has applications to the reliability theory of maintained systems.

If the components of a maintained coherent system have exponential lifetimes and NWU repair times, then an initially perfect system will have a NBU distribution of time until first system failure. Furthermore, transient availability is greater than steady-state availability.
The Generic Nature of Optimality Conditions in Nonlinear Programming
Authors: Spingarn J. E. , Rockafellar R. T.
Published: October 2008

First- and second-order optimality conditions are treated for parameterized classes of nonlinear programming problems in Rn. Under certain assumptions, it is shown that almost all problems in the class are such that every local minimizer satisfies the strong form of the optimality conditions.
Inequalities for the Completion Times of Stochastic PERT Networks
Authors: Devroye Luc P.
Published: October 2008

A stochastic PERT network is one in which the durations of the activities are random variables. In the absence of complete information about the distribution of these random variables or for the purpose of a fast rough analysis of the network, inequalities relating the mean E{T} and the variance σ2{T} of the completion time T of the project (network) to the means and the variances of the individual random variables can be useful. In this note new upper bounds for E{T} and σ2{T} are derived that are distribution free: they can be applied for all distributions of the durations of the activities.
Some Useful Functions for Functional Limit Theorems
Authors: Whitt Ward
Published: October 2008

Many useful descriptions of stochastic models can be obtained from functional limit theorems (invariance principles or weak convergence theorems for probability measures on function spaces). These descriptions typically come from standard functional limit theorems via the continuous mapping theorem. This paper facilitates applications of the continuous mapping theorem by determining when several important functions and sequences of functions preserve convergence. The functions considered are composition, addition, composition plus addition, multiplication, supremum, reflecting barrier, first passage time and time reversal. These functions provide means for proving new functional limit theorems from previous ones. These functions are useful, for example, to establish the stability or continuity of queues and other stochastic models.
Competitive Optimality of Logarithmic Investment
Authors: Bell Robert M. , Cover Thomas M.
Published: October 2008

Consider the two-person zero-sum game in which two investors are each allowed to invest in a market with stocks (X1, X2, …, Xm) ∼ F, where Xi ≥ 0. Each investor has one unit of capital. The goal is to achieve more money than one’s opponent. Allowable portfolio strategies are random investment policies B ∈ Rm, B ≥ 0, E ∑ mi = 1Bi = 1. The payoff to player 1 for policy B1 vs. B2 is P {Bt1 X ≥ Bt2 X}. The optimal policy is shown to be B* = Ub*, where U is a random variable uniformly distributed on [0, 2], and b* maximizes E ln bt X over b ≥ 0, ∑ bi = 1.

Curiously, this competitively optimal investment policy b* is the same policy that achieves the maximum possible growth rate of capital in repeated independent investments (Breiman [Breiman, L. 1961. Optimal gambling systems for favorable games. Fourth Berkeley Symposium. 1 65–78.] and Kelly [Kelly, J. 1956. A new interpretation of information rate. Bell System Tech. J. 917–926.]). Thus the immediate goal of outperforming another investor is perfectly compatible with maximizing the asymptotic rate of return.
Lexicographically Optimal Base of a Polymatroid with Respect to a Weight Vector
Authors: Fujishige Satoru
Published: October 2008

Let (E, ρ) be a polymatroid with a ground set E and a rank function ρ. A base x = (x(e))ϵ ∈ E of polymatroid (E, ρ) is called a lexicographically optimal base of (E, ρ) with respect to a weight vector w = (w(e))ϵ∈E if the |E|-tuple of the numbers x(e)/w(e)(e∈E) arranged in order of increasing magnitude is lexicographically maximum among all |E|-tuples of numbers y(e)/w(e)(e ∈ E) arranged in the same manner for all bases y = (y(e))e∈E of (E, ρ). We give theorems that characterize the relationship between weight vectors and lexicographically optimal bases and point out that a lexicographically optimal base minimizes among all bases a quadratic objective function defined in terms of the associated weight vector. Also, we present an algorithm for finding the (unique) lexicographically optimal base with respect to a given weight vector. Furthermore, we consider the problem of determining the set of weight vectors with respect to which a given base is lexicographically optimal and provide an algorithm for solving it, which is useful for the sensitivity analysis of the optimal base with regard to the variation of the weight vector. The algorithms proposed in the present paper efficiently solve the problem, treated by N. Megiddo, of finding a lexicographically optimal flow in a network with multiple sources and sinks, which is a special case of the problem considered here.
On the Exponent of a Primitive, Nearly Reducible Matrix
Authors: Brualdi Richard A. , Ross Jeffrey A.
Published: October 2008

An n × n nonnegative matrix is called nearly reducible provided it is irreducible and the replacement of any positive entry by zero yields a reducible matrix. The purpose of this article is to investigate the exponent γ(A) of an n × n primitive, nearly reducible matrix A (aperiodic, minimally strong directed graph). We prove that γ(A) ≥ 6 and that for each n ≥ 4 there exists a matrix A for which equality holds. We also show that γ(A) ≤ n2 − 4n + 6 and characterize those matrices for which equality holds. The proofs are carried out in the language of directed graphs.
Theoretical Efficiency of the Algorithm “Capacity” for the Maximum Flow Problem
Authors: Queyranne Maurice
Published: October 2008

The algorithm Capacity defined by Edmonds and Karp is an augmenting path algorithm which yields the maximum increase in flow value at each iteration. For networks with real capacities, we show that Capacity may require an infinite number of iterations, and an example of a “bad” network is produced. This result contrasts with the existence of other less “greedy” augmenting path algorithms which are always finite. However, we show that the sequence of flows constructed by Capacity converges toward a maximum flow. For networks with integer capacities, with a arcs and average capacity c̄, Edmonds and Karp’s upper bound of the order of O(a(log a + log c̄)) is derived and a class of networks is produced for which Capacity requires this number of iterations.
On the Optimality of (σ, S) Policies
Authors: Kalin Dieter
Published: October 2008

A standard periodic review, stochastic, dynamic multiproduct inventory model is considered in which the ordering cost consists of linear portions for each product and a setup cost. This setup cost is incurred if an order is placed for any number of products. There is no separate setup cost incurred for each product ordered. This basic problem has been studied by Johnson (Johnson, E. L. 1967. Optimality and computation of (σ, S) policies in the multi item-infinite horizon inventory problem. Management Sci. 13 475–491.) and Wheeler (Wheeler, A. 1968. Multiproduct inventory models with set-up. Technical report, Stanford University, Stanford.) among others. We extend their results by providing general conditions for the existence of an optimal policy and by further characterizing the optimal policy. In particular, we show that there exists an optimal (σ, S) policy. Such a policy does not order when the initial stock level is in σ and orders up to the vector level S otherwise (provided that such an order is feasible). Furthermore, the set σ is an upper layer (equivalently, an increasing set) with respect to a certain partial ordering. Such a policy reduces to an (s, S) policy in the single product case, in which case our conditions are very similar to those of Veinott (Veinott, A. F., Jr. 1966. On the optimality of (s, S) inventory policies. New conditions and a new proof. SIAM J. Appl. Math. 14 1067–1083.) and amount to a special case of the model of Schäl (Schäl, M. 1976. On the optimality of (s, S) policies in dynamic inventory models with finite horizon. SIAM J. Appl. Math. 30 518–537.). Our analysis is based in part on a generalization of quasi-convex functions (in the terminology of Porteus [Porteus, E. L. 1971. On the optimality of generalized (s, S) policies. Management Sci. 17 411–426.]). Finite and infinite horizon results are given.
On the Behavior of the Optimal Value Operator of Dynamic Programming
Authors: Klein Haneveld Willem K.
Published: October 2008

The optimality equation of discrete time dynamic programming is considered when state space and action space are finite dimensional Euclidean spaces. Based on a measurable selection theorem we give an elementary derivation of sufficient conditions to assure that the optimal value operator behaves well. For our model these conditions are weaker than those described in the existing literature. Under related conditions it is easy to prove that an optimal Markovian strategy exists for a finite stage Markovian stochastic optimization problem, and that the optimal strategies are completely characterized by the minimum sets of the optimality equations. This is illustrated with a general N-stage inventory control model.
On the Number of Component Failures in Systems Whose Component Lives are Exchangeable
Authors: Ross Sheldon M. , Shahshahani Mehrdad , Weiss Gideon
Published: October 2008

We consider a system that is composed of finitely many independent components each of which is either “on” or “off” at any time. The components are initially on and they have common on-time distributions. Once a component goes off, it remains off forever. The system is monotone in the sense that if the system is off whenever each component in a subset S (called a cut set) of components is off, then that is also true for every subset of components containing S.

We are interested in studying the properties of N, the number of components that are off at the moment the system goes off. We compute the factorial moments of N in terms of the reliability function. We also prove that N is an increasing failure rate average random variable and present a duality result. We consider the special structure in which the minimal cut sets do not overlap and we prove a conjecture of El-Neweihi, Proschan and Sethuraman which states that N is an increasing failure rate random variable. Then we consider the special case of nonoverlapping minimal path sets, and in the final section we present an application to a shock model.
Jackson’s Conjecture on Earliest Due Date Scheduling
Authors: Goldberg Henry M.
Published: October 2008

We discuss Jackson's conjecture on the optimality of the earliest due date scheduling rule in queueing systems. We investigate a single server queueing system with two due date classes of customers scheduled by an earliest due date rule allowing preemption. Using results from Goldberg’s analysis of EDD scheduling (Goldberg, H. M. 1977. Analysis of the earliest due date scheduling rule in queueing systems. Math. Oper. Res. 2 145–154.), we analytically describe relations for the distribution functions of virtual waiting time and their inverses, in transient as well as steady state. This leads to a proof of a more accurate statement than the conjecture for the model described.
Continuity of Generalized Semi-Markov Processes
Authors: Whitt Ward
Published: October 2008

It is shown that sequences of generalized semi-Markov processes converge in the sense of weak convergence of random functions if associated sequences of defining elements (initial distributions, transition functions and clock time distributions) converge. This continuity or stability is used to obtain information about invariant probability measures. It is shown that there exists an invariant probability measure for any finite-state generalized semi-Markov process in which each clock time distribution has a continuous c.d.f. and a finite mean. For generalized semi-Markov processes with unique invariant probability measures, sequences of invariant probability measures converge when associated sequences of defining elements converge. Hence, properties of invariant measures can be deduced from convenient approximations. For example, insensitivity properties established for special classes of generalized semi-Markov processes by Schassberger (Schassberger, R. 1977. Insensitivity of steady-state distributions of generalized semi-Markov processes, I. Ann. Probab. 5 87–99.), (Schassberger, R. 1978. Insensitivity of steady-state distributions of generalized semi-Markov processes, II. Ann. Probab. 6 85–93.), Konig and Jansen (König, D., U. Jansen. 1976. Eine Invarianzeigenschaft Zufälliger Bedienungs-Prozesse mit Positiven Geschwindigkeiten. Math Nachr. 70 321–364.), and Burman (Burman, D. Y. 1981. Insensitivity in queueing systems. Adv. Appl. Probab. To appear.) extend to a larger class of generalized semi-Markov processes.