bluuebunny/crossref_metadata_2025 huggingface dataset:
Pointwise and Uniformly Good Stationary Strategies for Dynamic Programming Models
Authors: van Dawen Rolf
Published: October 2008

This paper considers discrete time countable state Markovian decision problems with the total reward criterion. The main results are the following: a method for reducing the size of action sets for the given model without a loss in value, proof of the existence of pointwise good stationary strategies in the given model if such strategies exist in the embedded negative model and proof of the existence of uniformly good stationary strategies if pointwise good stationary strategies exist in the model.
Stochastic Comparisons for Non-Markov Processes
Authors: Whitt Ward
Published: October 2008

A technique is developed for comparing a non-Markov process to a Markov process on a general state space with many possible stochastic orderings. Two such comparisons with a common Markov process yield a comparison between two non-Markov processes. The technique, which is based on stochastic monotonicity of the Markov process, yields stochastic comparisons of the limiting distributions and the marginal distributions at single time points, but not the joint distributions. These stochastic comparisons are obtained under the condition that the one-step transition probabilities (in discrete time) or infinitesimal transition rates (in continuous time) are appropriately ordered, uniformly in the extra information needed to add to the state to make the non-Markov process Markov. The technique is illustrated by establishing an inequality in traffic theory concerning the blocking in multi-server service facilities when each customer requires service from several facilities simultaneously.
A Zero-Sum Game with Incomplete Information and Compact Action Spaces
Authors: Mamer John W. , Schilling Kenneth E.
Published: October 2008

We make use of distributional strategies to describe player's choices of actions in a zero-sum game with incomplete information and compact action spaces. Under very mild assumptions we obtain the existence of equilibria.
Random Binary Search: A Randomizing Algorithm for Global Optimization in $R^1$
Authors: Zemel Eitan
Published: October 2008

Randomizing (stochastic) global optimization algorithms can be viewed as sampling procedures, where at each iteration a local optimum is sampled from the set of local optima. The effectiveness of such an algorithm depends crucially on the sampling distribution, i.e., on the probabilities of sampling the various local optima. There exists a very large body of research on stochastic global optimization. However, very little is known about the sampling distribution itself and, in particular, on the specific way in which it depends on the function being optimized, on the region in which the search takes place, and on the optimization routine. In this paper we set out to examine these issues in some detail and present some first results in this direction. The case analyzed in this paper is the optimization of a one-dimensional function using a randomizing version of binary search. We give an effective (computable in quadratic time) formula for the sampling distribution and obtain various interesting properties of this distribution which are relevant to the behavior of the algorithm in practice. We also discuss some issues related to adaptive search.
Equivalence of Solutions to Network Location Problems
Authors: Hansen P. , Thisse J.-F. , Wendell R. E.
Published: October 2008

This paper compares solution concepts associated with three location problems on a network: (i) a single-facility distance minimization problem; (ii) a two-facility spatial competition problem; and (iii) a single-facility locational voting problem. It is shown that the three problems have a common global solution when the network exhibits a property of symmetry around a point. For more general networks, this ceases to be true for global solutions but an identity holds for local solutions.
Letter To The Editor: On Borwein's Paper, “Adjoint Process Duality”
Authors: Zălinescu Constantin
Published: October 2008

We give counterexamples for some statements of Borwein and sufficient conditions for the validity of these.
The A-Forest Iteration Method for the Stochastic Generalized Transportation Problem
Authors: Qi Liqun
Published: October 2008

The stochastic generalized transportation problem (SGTP) is a stochastic program with simple recourse where the master problem is a generalized transportation problem. The graph corresponding to an optimal solution of an SGTP can be characterized as an A-forest each of its connected subgraphs is either a tree or a one-loop tree. We propose here a finitely convergent method to solve the SGTP. The iteration techniques constitute some modifications of those for the forest iteration method for solving the stochastic transportation problem, which was given in a previous paper. A small numerical example is also presented.
A Linearization Method for Nonsmooth Stochastic Programming Problems
Authors: Ruszczyński Andrzej
Published: October 2008

For a stochastic programming problem with a nonsmooth objective a recursive stochastic subgradient method is proposed in which successive directions are obtained from quadratic programming subproblems. The subproblems result from linearization of original constrains and from approximation of the objective by a quadratic function involving stochastic ϵ-subgradient estimates constructed in the course of computation. A special Lyapunov function technique is used to show that the method is convergent with probability 1 to stationary points and recovers the subgradient and Lagrange multipliers that appear in necessary conditions of optimality.
Ordered Solutions for Dynamic Programs
Authors: Lovejoy William S.
Published: October 2008

Suppose X indexes a collection of optimization problems in Rn and δ*(x) is an optimal program for the problem indexed by x ∈ X. Sufficient conditions are presented for two other families of optimization problems to possess optimal programs δ0(x) and δ0(x) (for the respective problems when x ∈ X) such that δ0(x) ≤ δ*(x) ≤ δ0(x) for all x ∈ X. This result is then applied to obtain bounds on an optimal policy in the class of dynamic programs which are bounded, monotone contractions.
Verification of High Order Optimality Conditions Using the Polyadic Representation of Derivatives
Authors: McCormick Garth P.
Published: October 2008

Conditions involving derivatives higher than the second must be checked if the first and second optimality conditions fail to determine whether or not a point locally minimizes an unconstrained function. An implementable inductive algorithm for doing this is developed based on the presentation of higher derivatives by sums of symmetric polyads (generalized outer product matrices). A set of equations is developed which must be satisfied for the odd order conditions to hold. Checking the even order conditions involves the solution of successive nonconvex programming problems. An example is included.
Simplicial Variable Dimension Algorithms for Solving the Nonlinear Complementarity Problem on a Product of Unit Simplices Using a General Labelling
Authors: van der Laan G. , Talman A. J. J. , van der Heyden L.
Published: October 2008

This paper deals with the nonlinear complementarity problem on the product space of unit simplices, S. A simplicial variable dimension algorithm developed by van der Laan and Talman for proper labellings of S is extended to the case of general labellings. General labellings allow a more natural description of the complementarity problem on the boundary of S. A distinctive feature of the new algorithm is that lower dimensional simplicial movement can occur both on the boundary and in the interior of S. In contrast, the van der Laan and Talman algorithm for proper labellings of S allows lower dimensional simplicial movement only in the interior of S. Computational experiments confirm the usefulness of general labellings for solving nonlinear complementarity problems.
An Algorithm for Global Minimization of Linearly Constrained Concave Quadratic Functions
Authors: Kalantari B. , Rosen J. B.
Published: October 2008

We present an algorithm for the global minimization of a quadratic function ψ(x, y) = −½xTQx + hTx + dTy, over a polytope Ω = {(x, y) ∈ ℝn+k: Ax + By ≤ b, x ≥ 0, y ≥ 0}, where x, h ∈ ℝn, y, d ∈ ℛk, b ∈ ℛm, and where A and B are m × n and m × k matrices, respectively, and Q is an n × n symmetric positive definite matrix.

We first consider the case where k = 0 and construct a “tight” parallelpiped R, containing Ω by using an arbitrary set of Q-conjugate directions and by solving 2n linear programs. We show that the convex envelope of ψ with respect to R is linear and obtain an explicit formula for it. We then describe a branch and bound algorithm in which the linearity of the convex envelope allows efficient lower bounding for the subproblems. For each subproblem we obtain the linear convex envelope of ψ over a smaller parallelepiped, R′, with facets parallel to those of R. Then, we obtain a lower bound by minimizing this convex envelope over R′ ∩ Ω. If ψ* is the optimal objective value, for each ϵ ≥ 0, the algorithm generates a sequence of feasible points zj with nonincreasing function values ψj and a nondecreasing sequence Γj, of lower bounds to ψ*. Moreover if ϵ > 0, there exist j0 such that (ψj − Γj) ≤ ϵ for all j ≥ j0, and if ϵ = 0, (ψj − Γj) converges to 0. The results are then generalized to the case where k is nonzero and possibly much larger than n. Preliminary computational results are also presented.
IFRA Properties of Some Markov Jump Processes with General State Space
Authors: Shaked Moshe , Shanthikumar J. George
Published: October 2008

Consider a stochastically monotone increasing regular Markov jump process on a partially ordered measurable space 𝒳. It is shown that the first passage time to any upper set U is IFRA. A conjecture of Brown and Chaganty (Brown, M., Chaganty, N. R. 1983. On the first passage time distribution for a class of Markov chains. Ann. Probab. 11 1000–1008.) is verified and results of Brown and Chaganty (Brown, M., Chaganty, N. R. 1983. On the first passage time distribution for a class of Markov chains. Ann. Probab. 11 1000–1008.) and of Ross (Ross, S. M. 1981. Generalized Poisson shock models. Ann. Probab. 9 896–898.) are extended.
Coherent Continuous Systems and the Generalized Functional Equation of Associativity
Authors: Mak King-Tim
Published: October 2008

A theory of coherent continuous systems is outlined. Systems are to be decomposed hierarchically into modules. For this purpose, some results on the structure of continuous functions are adapted to generalize the classic 3-Modules Theorem of binary systems. Consideration of the modular structure of coherent continuous systems leads naturally to the generalized functional equation of associativity G(g(u, v), w) = H(u, h(v, w)) involving four unknown 2-place continuous functions. The functional equation is solved under some regularity conditions motivated by the properties of coherent continuous systems. The solutions obtained give rise to generalized notions of parallel and series system structures.
α-Stable Extensive Game Forms
Authors: Ichiishi Tatsuro
Published: October 2008

Peleg established a fundamental theorem which says that convex effectivity functions are stable. He also proved its partial converse: Within the class of maximal effectivity functions, stability implies convexity. The present paper provides another partial converse: Within the class of α-effectivity functions derived from extensive game forms (without chance moves), stability implies convexity. It also provides a geometric characterization of the stability condition for the latter class.
Send-and-Split Method for Minimum-Concave-Cost Network Flows
Authors: Erickson Ranel E. , Monma Clyde L. , Veinott Arthur F.
Published: October 2008

Many problems from inventory, production and capacity planning, and from network design, exhibit scale economies and can be formulated in terms of finding minimum-additive-concave-cost nonnegative network flows. We reduce the problem to an equivalent one in which the arc flow costs are nonnegative and give a dynamic-programming method, called the send-and-split method, to solve it. The main work of the method entails repeatedly solving set-splitting and minimum-cost-chain problems. In uncapacitated networks with n nodes, a arcs, and d + 1 demand nodes, i.e., nodes with nonzero exogenous demand, the algorithm requires up to n2−13d + s2d operations (additions and comparisons) where s = n log2n + 3a is the number of operations required to solve a minimum-cost-chain problem with nonnegative arc costs on the augmented graph formed by appending a node and an arc thereto from each node in the graph. If also the network is k-planar, i.e., the graph is planar with all demand nodes lying on the boundary of k faces, the method requires at most n2−kd3k + sd2k operations. The algorithm can be applied to capacitated networks because they can be reduced to equivalent uncapacitated ones. These results unify, significantly generalize (e.g., to cyclic problems), and sometimes improve upon (e.g., for tandem facilities) known polynomial-time dynamic-programming algorithms for Wagner and Whitin's (Wagner, H. M., Whitin, T. M. 1958. Dynamic version of the economic lot size model. Management Sci. 5 89–96.) dynamic economic-order-quantity problem, Zangwill's (Zangwill, W. I. 1969. A backlogging model and a multi-echelon model of a dynamic economic lot size production system—A network approach. Management Sci. 15 506–527.) generalization to tandem facilities, and Veinott's (Veinott, Jr., A. F. 1969. Minimum concave-cost solution of Leontief substitution models of multi-facility inventory systems. Oper. Res. 17 262–291.) increasing-capacity warehousing problem. The networks for the finite-period versions of these problems are each 1-planar. The method improves upon Zangwill's (Zangwill, W. I. 1968. Minimum concave cost flows in certain networks. Management Sci. 14 429–450.) related O(and) running-time dynamic-programming method for finding minimum-additive-concave-cost non-negative flows in circuitless single-source networks. We also implement the method to solve in polynomial time the (d + 1)-demand-node and k-planar versions of the minimum-cost forest and Steiner problems in graphs. The running time for the (d + 1)-demand-node Steiner problem in graphs is comparable to that of Dreyfus and Wagner's (Dreyfus, S. E., Wagner, R. A. 1971. The Steiner problem in graphs. Networks 1 195–207.) method.
Infinite Channel Queueing System with Controlled Input
Authors: Dshalalow Jewgeni
Published: October 2008

We study a queueing model of type G⃗/M/∞ with a nonrecurrent input. The intensity of the input stream is regulated at epochs of successive starts of customers moving from the source to the system, and it is dependent on the number of busy channels. We consider three groups of channels. Such a division is connected with different expenditures of servicing within each of the groups. It is worthwhile to control the input rate in order to minimize the long-run average cost. The basic process is the number of busy channels. We derive its limiting distribution explicitly by introducing an auxiliary two-dimensional Markov process and treating the corresponding Kolmogorov system of differential equations. We also use some properties of semiregenerative processes. The limiting distributions are used to solve an optimization problem.
Exponential Convergence in Undiscounted Continuous-Time Markov Decision Chains
Authors: Zijm W. H. M.
Published: October 2008

In this paper, we analyze the asymptotic behaviour of the value function v(t) of an undiscounted continuous-time Markov decision chain. Both the state space and the action space are assumed to be finite. A new proof of the convergence of v(t) − tg is presented (where g denotes the maximal expected average reward over an infinite time horizon). Moreover, it is shown that this convergence is exponential.
The d-Step Conjecture and Its Relatives
Authors: Klee Victor , Kleinschmidt Peter
Published: October 2008

The d-step conjecture arose from an attempt to understand the computational complexity of edge-following algorithms for linear programming, such as the simplex algorithm. It can be stated in terms of diameters of graphs of convex polytopes, in terms of the existence of nonrevisiting paths in such graphs, in terms of an exchange process for simplicial bases of a vector space, and in terms of matrix pivot operations. First formulated by W. M. Hirsch in 1957, the conjecture remains unsettled, though it has been proved in many special cases and counterexamples have been found for slightly stronger conjectures. If the conjecture is false, as we believe to be the case, then finding a counterexample will be merely a small first step in the line of investigation related to the conjecture. This report summarizes what is known about the d-step conjecture and its relatives. A considerable amount of new material is included, but it does not seem to come close to settling the conjecture. Of special interest is the first example of a polytope that is not vertex-decomposable, showing that a certain natural approach to the conjecture will not work. Also significant are the quantitative relations among the lengths of paths associated with various forms of the conjecture.
Optimal Bin Packing with Items of Random Sizes
Authors: Rhee Wansoo T.
Published: October 2008

Consider a probability μ on [0, 1] and i.i.d. random variables X1, X2, …, Xn distributed like μ. Let Qn denote the optimal (minimum) number of unit size bins needed to pack items of size X1, X2, …, Xn. We characterize the class of μ which have the property that limn→∞ Qn/n = E(X1) a.s., or equivalently that the expected level of occupancy of bins converges to one.
Discrete Event Dynamic Programming with Simultaneous Events
Authors: L'Ecuyer Pierre , Haurie Alain
Published: October 2008

This paper deals with an infinite-horizon discrete-event dynamic programming model with discounting, and with Borel state and action spaces. Instead of the usual n-stage contraction assumption (Denardo, E. V. 1967. Contraction mappings in the theory underlying dynamic programming. SIAM Rev. 9 165–177.), uniform over all admissible state-action pairs, we propose milder conditions, sufficient for regularity, and allowing any number of simultaneous events. This model permits one to treat properly a number of problems typically associated with continuous-time maintenance models (Haurie, A., L'Ecuyer, P. 1982. A stochastic control approach to group preventive replacement in a multicomponent system. IEEE Trans. Automat. Control AC-27 387–393; Haurie, A., L'Ecuyer, P. 1986. Approximation and bounds in discrete event dynamic programming. IEEE Trans. Automat. Control AC-31 227–235; L'Ecuyer, P. 1983. Processus de décision markoviens à étapes discrètes: Application à des problèmes de remplacement d'équipement. Ph.D. thesis (in French), published in Les cahiers du GERAD, report no. G-83-06, Ecole des H. E. C., Montreal; L'Ecuyer, P., Haurie, A. 1987. The repair vs replacement problem: A stochastic control approach. Optim. Control Appl. Meth. 8 219–230.). The main results concern the uniform convergence of the dynamic programming (DP) procedure to the optimal cost-to-go function, the existence of an ϵ-optimal policy for any ϵ > 0, and a set of sufficient conditions for the convergence of the DP procedure to an optimal policy.
The Fair Resource Allocation Problem with Submodular Constraints
Authors: Fujishige Satoru , Katoh Naoki , Ichimori Tetsuo
Published: October 2008

The problem of allocating a limited resource to relevant activities in a fair manner on the basis of a certain general objective function has recently been considered by N. Katoh, T. Ibaraki, and H. Mine. We generalize Katoh, Ibaraki, and Mine's problem to the one with a feasible region expressed by a submodular function and give an efficient solution algorithm. The proposed algorithm is of the same complexity as and simpler than Katoh, Ibaraki, and Mine's when specialized to their problem.
NP-Hard, Capacitated, Balanced p-Median Problems on a Chain Graph with a Continuum of Link Demands
Authors: Sherali Hanif D. , Nordai Frederick L.
Published: October 2008

This paper introduces the analysis of capacitated p-median location-allocation problems on networks in which there may exist a continuum of demand on the links characterized by some demand distribution or density functions. We address the particular case of locating a given set of p capacitated facilities on a chain graph for which the total supply is equal to the total expected demand. This problem is demonstrated to be NP-hard, even when the demand is discrete and restricted to occur only at the nodes of the chain graph, or when the demand density function is symmetric and unimodal. However, the separate location and allocation subproblems are efficiently solvable, and provide a useful characterization for an optimal solution to the p-median problem. Based on this characterization, we analyze the monotone demand distribution case which admits a closed form greedy solution, and we also analyze problems having nonsymmetric or symmetric unimodal demand distributions. This analysis lays the groundwork for an enumerative type of algorithm for problems with more general demand distribution functions.
On the First Failure Time of Dependent Multicomponent Reliability Systems
Authors: Shaked Moshe , Shanthikumar J. George
Published: October 2008

In this paper multicomponent reliability systems are considered, where component failure and repair completion rates depend on the state, ages and current repair durations of the other components. This is a generalization of a model of Ross (Ross, S. M. 1984. A model in which component failure rates depend on working set. Naval Res. Logist. Quart. 31 297–300.). Sufficient conditions on the sets of rates which imply stochastic ordering between first failure times of two such systems are found. Sufficient conditions on the rates which imply that the first failure time of such a system is new better than used (NBU) are given. Some results of Barlow and Proschan (Barlow, R. E., Proschan, F. 1976. Theory of maintained systems: Distribution of time to first system failure. Math. Oper. Res. 1 32–42.), Chiang and Niu (Chiang, D. T., Niu, S. C. 1980. On the distribution of time to first system failure. J. Appl. Probab. 17 481–489.), and Ross (Ross, S. M. 1976. On the time to first failure in multicomponent exponential reliability systems. Stochastic Process. Appl. 4 167–173.) are obtained as special cases. A counterexample to an apparently stronger result of Miller (Miller, D. R. 1979. Almost sure comparison of renewal processes and poisson processes, with application to reliability theory. Math. Oper. Res. 4 406–413.) is also given. Further results and a discussion are included.
Convergence of Lagrange Multipliers and Dual Variables for Convex Optimization Problems
Authors: Back Kerry
Published: October 2008

Sufficient conditions are given for the limit of a net of Lagrange multipliers for convex optimization problems to be a Lagrange multiplier for the limit problem. The distinct issue of convergence of solutions to dual problems is also addressed, using a continuity property of the Fenchel transform.
Probabilistic Analysis of the Capacitated Transportation Problem
Authors: Hassin Refael , Zemel Eitan
Published: October 2008

We consider the capacitated transportation problem defined by sets of supplies ai, i ∈ I, demands bj, j ∈ J, and capacities cij, i ∈ I, j ∈ J. Assuming that the capacities are random variables, we prove asymptotic conditions on the supplies and demands which assure that a feasible solution exists almost surely. The proof is constructive and supplies an algorithm whose running time is O(| I| |J|). We then apply the results to the maximum flow problem.
An Almost Linear-Time Algorithm for Graph Realization
Authors: Bixby Robert E. , Wagner Donald K.
Published: October 2008

Given a {0, 1}-matrix M, the graph-realization problem for M is to find a tree T such that the columns of M are incidence vectors of paths in T, or to show that no such T exists. An algorithm is presented for this problem the time complexity of which is very nearly linear in the number of ones in M.
Some Bounds for the Banzhaf Index and Other Semivalues
Authors: Holzman Ron , Lehrer Ehud , Linial Nathan
Published: October 2008

The normalized Banzhaf index of a player in a monotone simple game (thought of as a voting model) is the probability for that player to swing the outcome of the vote. We bound the Euclidean norm of the vector of Banzhaf indices of simple games in terms of the number winning coalitions. The Banzhaf index is a semivalue, so we proceed to estimate norms of general semivalues.
Continuous-Time Casino Problems
Authors: Pestien Victor C. , Sudderth William D.
Published: October 2008

A gambler or an investor seeks to increase his fortune by a given amount before going bankrupt. The problem can be formulated as a stochastic control problem on an interval and is called a “continuous-time casino” if certain natural conditions are satisfied. An explicit formula is given for the value function of such a problem and the collection of optimal strategies is determined. “Fair casinos” are characterized in a result analogous to one of L. E. Dubins and L. J. Savage for discrete-time problems.
Some Lattice-Theoretic Tools for Network Reliability Analysis
Authors: Bienstock Daniel
Published: October 2008

The computation of K-terminal reliability for a graph is an intractable problem, and polynomially bounded algorithms are known for very limited classes of graphs only. This paper presents lattice-theoretic speed-up techniques for existing algorithmic ideas.
Weighted Majority Games Have Asymptotic Value
Authors: Neyman Abraham
Published: October 2008

The asymptotic value of a game v with a continuum set of players, I, is defined whenever all the sequences of the Shapley values of finite games that “approximate” v have the same limit. A weighted majority game is a game of the form f ∘ μ where μ is a positive measure and f(x) = 1 if x ≥ q and f(x) = 0 otherwise, and q is a real number, 0 < q < μ(I). In this paper we prove that all weighted majority games have asymptotic values. This result is then used further to show that if v is of the form v = f ∘ μ, where μ is a probability measure and f is a function of bounded variation on [0, 1] that is continuous at 0 and at 1, then v has an asymptotic value. This bad previously been known only when f is absolutely continuous, or when μ has at most finitely many atoms or when μ is purely atomic. Thus, the essential novelty is that even when μ has countably many atoms and a nonatomic part, f ∘ μ has an asymptotic value. We also show that f ∘ μ does not necessarily have an asymptotic value when μ is a signed measure.
Extreme Points of Moment Sets
Authors: Winkler Gerhard
Published: October 2008

The extreme points of sets of probability measures—determined by a finite number of generalized moment conditions—are characterized. Together with an integral representation theorem the characterization is used to optimize affine functionals.
A Limit Theorem for (min, +) Matrix Multiplication
Authors: Saks Michael E.
Published: October 2008

A natural model for the sequential performance of tasks involves a system that can be configured into any one of a possible set S of states where the cost of performing a given task depends on the state. The cost of processing a sequence of tasks (taken from a set T of possible tasks) is the sum of the costs of performing each task plus the cost incurred by moving between states. A quantity of interest is the supremum over all task sequences of the average cost per task to process the sequence. We answer a question of R. Graham by proving that when the underlying costs are integral this supremum is rational.
Directional Behaviour of Optimal Solutions in Nonlinear Mathematical Programming
Authors: Gauvin Jacques , Janin Robert
Published: October 2008

This paper is concerned with Holder, Lipschitz and differential properties of the optimal solutions of a nonlinear mathematical programming problem with perturbations in some fixed direction. These properties are obtained with virtually minimal regularity conditions using an approach based on duality and stability. The Holder property is used to obtain the directional derivative for the optimal value function.
Ordinary CLT and WLLN Versions of L = λW
Authors: Glynn Peter W. , Whitt Ward
Published: October 2008

The familiar queueing principle expressed by the formula L = λW (Little's law) can be interpreted as a relation among strong laws of large numbers (SLLNs). Here we prove central-limit-theorem (CLT) and weak-law-of-large-numbers (WLLN) versions of L = λW. For example, if the sequence of ordered pairs of interarrival times and waiting times is strictly stationary and satisfies a joint CLT, then the queue-length process also obeys a CLT with a related limiting distribution. In a previous paper we proved a functional-central-limit-theorem version of L = λW, without stationarity, by very different arguments. The two papers highlight the differences between establishing ordinary limit theorems and their functional-limit-theorem counterparts.
An Algorithm for a Dynamic Programming Model of Fractional Flows
Authors: Flynn James
Published: October 2008

In an earlier paper, the author introduced an n-dimensional dynamic programming model of fractional flows, characterized its solutions under general conditions, and developed methods for their computation. The latter, which resemble algorithms for n-state Markovian decision processes, break down when the costs are undiscounted and the flow matrices are nontransient. Here, an algorithm is presented that computes many of the quantities of interest more efficiently under milder assumptions. In addition, some of our earlier results for the undiscounted case are extended to models with nontransient flow matrices.
Variance-Penalized Markov Decision Processes
Authors: Filar Jerzy A. , Kallenberg L. C. M. , Lee Huey-Miin
Published: October 2008

We consider a Markov decision process with both the expected limiting average, and the discounted total return criteria, appropriately modified to include a penalty for the variability in the stream of rewards. In both cases we formulate appropriate nonlinear programs in the space of state-action frequencies (averaged, or discounted) whose optimal solutions are shown to be related to the optimal policies in the corresponding “variance-penalized MDP.” The analysis of one of the discounted cases is facilitated by the introduction of a “Cartesian product of two independent MDPs.”
A Strongly Polynomial Algorithm for Minimum Cost Submodular Flow Problems
Authors: Fujishige Satoru , Röck Hans , Zimmermann Uwe
Published: October 2008

The only known strongly polynomial algorithm for solving minimum cost submodular flow problems is due to Frank and Tardos (Frank, A., É. Tardos. 1985. An application of the simultaneous approximation in combinatorial optimization. Report No. 85375, Institut für Ökonometrie und Operations Research, Bonn, May.) and is based on the simultaneous approximation algorithm of Lenstra, Lenstra, and Lovász (Lenstra, A. K., H. W. Lenstra, L. Lovász. 1982. Factoring polynomials with rational coefficients. Math. Ann. 261 515–534.). We propose a purely combinatorial strongly polynomial algorithm. It consists in solving a sequence of at most m + n(n − 1) minimum cost submodular flow problems with cost coefficients bounded by n2, where n is the number of the vertices and m is the number of the arcs in the underlying graph. The current cost coefficients are calculated by means of tree projection and scaling.
Boundary Behavior of Interior Point Algorithms in Linear Programming
Authors: Megiddo Nimrod , Shub Michael
Published: October 2008

This paper studies the boundary behavior of some interior point algorithms for linear programming. The algorithms considered are Karmarkar's projective rescaling algorithm, the linear rescaling algorithm which was proposed as a variation on Karmarkar's algorithm, and the logarithmic barrier technique. The study includes both the continuous trajectories of the vector fields induced by these algorithms and also the discrete orbits. It is shown that, although the algorithms are defined on the interior of the feasible polyhedron, they actually determine differentiable vector fields on the closed polyhedron. Conditions are given under which a vector field gives rise to trajectories that each visit the neighborhoods of all the vertices of the Klee-Minty cube. The linear rescaling algorithm satisfies these conditions. Thus, limits of such trajectories, obtained when a starting point is pushed to the boundary, may have an exponential number of breakpoints. It is shown that limits of projective rescaling trajectories may have a linear number of such breakpoints. However, projective rescaling trajectories may visit the neighborhoods of linearly many vertices. The behavior of the linear rescaling algorithm near vertices is analyzed. It is proved that all the trajectories have a unique asymptotic direction of convergence to the optimum.
The Projective SUMT Method for Convex Programming
Authors: McCormick Garth P.
Published: October 2008

An algorithm for solving convex programming problems is derived from the differential equation characterizing the trajectory of unconstrained minimizers of the classical logarithmic barrier function. Convergence of the continuous version of this projective SUMT method is proved under minimal assumptions. Extension of the algorithm to a form which handles linear equality constraints produces a differential equation analogue of Karmarkar's method for linear programming. The discrete version uses the same method of search and finds the step size by minimizing the logarithmic method of centers function. An acceleration procedure based on the nonvanishing of the Jacobian of the Karush-Kuhn-Tucker system at a minimizer is shown to converge quadratically. When the problem variables are bounded, dual feasible points are available and the algorithm produces at each iteration lower and upper bounds on the global minimum. A matrix approximation is given which greatly reduces the traditional problems in inverting the badly conditioned matrix used to generate the directions of search.
On Global Costs and Nyquist's Theorem in Random Variate Generation
Authors: Devroye Luc
Published: October 2008

We consider a large class of densities defined in terms of smoothness and tail conditions. Assume that we want to generate n iid random variables from a given density f in this class, and that the global cost of the generator is equal to the total number of evaluations of f. We demonstrate with the help of several examples how one can proceed to make the expected cost grow at a sublinear (o(n)) rate. Examples include the class of Lipschitz densities on [0, 1] with known Lipschitz constant, the class of bounded monotone densities on [0, 1], and the class of all densities with a characteristic function of bounded support and kth moment bounded by a given constant. In the last example, we proceed to show how Nyquist's theorem can be exploited to yield a generator with O(n1/(k−1)) expected cost.
On the Rate of Convergence of Some Stochastic Processes
Authors: Kern Walter
Published: October 2008

We present a general technique for obtaining bounds on the deviation of the optimal value of some stochastic combinatorial problems from their mean. As a particular application, we prove an exponential rate of convergence for the length of a shortest path through n random points in the unit square. This strengthens a previous result of Steele (Steele, J. M. 1981. Complete convergence of short paths and Karp's algorithm for the TPS. Math. Oper. Res.).
Duality and Other Results for M/G/1 and GI/M/1 Queues, Via a New Ballot Theorem
Authors: Niu Shun-Chen , Cooper Robert B.
Published: October 2008

We generalize the classical ballot theorem and use it to obtain direct probabilistic derivations of some well-known and some new results relating to busy and idle periods and waiting times in M/G/1 and GI/M/1 queues. In particular, we uncover a duality relation between the joint distribution of several variables associated with the busy cycle in M/G/1 and the corresponding joint distribution in GI/M/1. In contrast with the classical derivations of queueing theory, our arguments avoid the use of transforms, and thereby provide insight and term-by-term “explanations” for the remarkable forms of some of these results.
Asymptotic Behaviour of Optimal Control Systems with Low Discount Rates
Authors: Colonius Fritz
Published: October 2008

Let x be the path and u the control that maximizes the cumulative return discounted at rate δ. The purpose is to analyze the dependence of x and u on the rate δ. Under certain conditions, as δ tends to 0, the corresponding solution (x, u) tends to the solution for rate 0. We use results from geometric control theory and the theory of semiflows.
A Simplicial Algorithm for Stationary Point Problems on Polytopes
Authors: Talman A. J. J. , Yamamoto Y.
Published: October 2008

A simplicial variable dimension restart algorithm for the stationary point problem or variational inequality problem on a polytope is proposed. Given a polytope C in ℝn and a continuous function f: C → ℝn, find a point ◯ in C such that f(◯) · ◯ ≥ f(◯) · x for any point x in C. Starting from an arbitrary point v in C, the algorithm generates a piecewise linear path of points in C. This path is followed by alternating linear programming pivot steps to follow a linear piece of the path and replacement steps in a simplicial subdivision of C. Within a finite number of function evaluations and linear programming pivot steps the algorithm finds an approximate stationary point. The algorithm leaves the starting point v along a ray pointing to one of the vertices w of C. The vertex w is obtained from the optimum solution of the linear programming problem maximize f(v) · x subject to x ∈ C.
Sensitivity Analysis for Variational Inequalities Defined on Polyhedral Sets
Authors: Qiu Yuping , Magnanti Thomas L.
Published: October 2008

Variational inequalities have often been used as a mathematical programming tool in modeling various equilibria in economics and transportation science. The behavior of such equilibrium solutions as a result of the changes in problem data is always of concern. In this paper, we present an approach for conducting sensitivity analysis of variational inequalities defined on polyhedral sets. We introduce the notion of differentiability of a point-to-set mapping and derive continuity and differentiability properties regarding the perturbed equilibrium solutions, even when the solution is not unique. As illustrated by several examples, the assumptions made in this paper are in a certain sense the weakest possible conditions under which the stated properties are valid. We also discuss applications to some equilibrium problems such as the traffic equilibrium problem.
Approximating an Infinite Stage Search Problem with a Finite Horizon Model
Authors: Wilson John G.
Published: October 2008

A target is moving randomly on a lattice. A searcher, starting at the origin, wants to follow a search plan that has minimum expected cost. Very general cost functions are allowed. The cost function depends on the time to capture and the search procedure followed. At each stage, the searcher can move only to adjacent positions or remain at his current position. The target's motion may depend on the search procedure, thus allowing for the possibility that the target may take evasive action. It is shown that only a finite number of plans need to be considered in order to approximate the optimal cost. It is also shown that the leading elements of optimal finite horizon plans eventually become the leading elements of optimal infinite horizon plans. The case of search on the real line, where the cost is O(τk), where k ≥ 1 and τ is the time to capture, is considered in detail. The results of this paper also generalise the important planning horizon theorems of Bean and Smith (Bean, J. C., Smith, R. L. 1984. Conditions for the existence of planning horizons. Math. Oper. Res. 9 391–401.).
Zero Investment in a High Yield Asset Can be Optimal
Authors: Xu Gan-Lin
Published: October 2008

In a market with one stock and one bond, a risk averse agent would normally follow the principle of holding a positive amount of stock if and only if its mean rate of return is strictly larger than the interest rate of the bond. We provide an example to show that in the latter case it may be optimal not to invest in the stock.
A Theory on Extending Algorithms for Parametric Problems
Authors: Eaves B. Curtis , Rothblum Uriel G.
Published: October 2008

Given certain algorithms for certain problems, these algorithms can be incorporated in a lift, solve, and lower sequence to form algorithms for solving parametric versions of the problems. In the first phase of the sequence the parametric problem is lifted to an extended ordered field where it becomes a single nonparametric problem. Second, the original algorithm is run in the extended ordered field to solve the single problem. Finally, this solution to the single problem is lowered to the original ordered field to obtain a parametric solution to the original parametric problem.
On Waiting for Simultaneous Access to Two Resources
Authors: Honig Michael L. , Ott Teunis J.
Published: October 2008

This paper studies the M/G/1 queue where a special (test) customer can get service only if he has simultaneous access to the server and a second resource. All other customers only need access to the server. The second resource becomes available after an exponentially distributed amount of time. The ordinary customers are served according to the FIFO discipline. The test customer has the freedom to leave his place in the queue at any time and join the end of the queue. If he reaches the server before the second resource becomes available, he then must return to the back of the queue.

We derive the waiting time distribution of the test customer given that he always maintains his position in the queue until he reaches the server. A number of conditions are given under which this “move-along” policy is optimal, i.e., minimizes the test customer's mean delay until service. These conditions depend on the amount of information and freedom of action available to the test customer.
Generalized Delta Theorems for Multivalued Mappings and Measurable Selections
Authors: King Alan J.
Published: October 2008

The classical delta theorem can be generalized in a mathematically satisfying way to a broad class of multivalued and/or nonsmooth mappings, by examining the convergence in distribution of the sequence of difference quotients from the perspectives of recent developments in convergence theory for random closed sets and new descriptions of first-order behaviour of multivalued mappings. Such a theory opens the way to applications of asymptotic techniques in many areas of mathematical optimization where randomness and uncertainty play a role. Of special importance is the asymptotic convergence of measurable selections of multifunctions when the limit multifunction is single-valued almost surely.
Simulation Output Analysis Using Standardized Time Series
Authors: Glynn Peter W. , Iglehart Donald L.
Published: October 2008

The method of standardized time series (STS) was proposed by Schruben as an approach for constructing asymptotic confidence intervals for the steady-state mean from a single simulation run. The STS method “cancels out” the variance constant while other methods attempt to consistently estimate the variance constant. Our goal in this paper is to generalize the STS method and to study some of its basic properties. Starting from a functional central limit theorem (FCLT) for the sample mean of the simulated process, a class of mappings of C[0,1] to ℝ is identified, each of which leads to a STS confidence interval. One of these mappings leads to the batch means method. A lower bound is obtained for the expected length of the asymptotic (as the run size becomes large) STS confidence intervals. This lower bound is not attained, but can be approached arbitrarily closely, by STS confidence intervals. Methods that consistently estimate the variance constant do realize this lower bound. The variance of the length of a STS confidence interval is of larger order (in the run length) than is that for the regenerative method.
Evaluating Strategies for Markov Decision Processes in Parallel
Authors: Glazebrook K. D. , Fay N. A.
Published: October 2008

The authors' work on the use of Gittins indices in the evaluation of strategies for families of alternative bandit processes has found many applications. Among these are procedures for sensitivity analysis in stochastic scheduling. This theoretical paper aims at developing results which will form the basis of an approach to strategy evaluation for a class of processes of greater complexity. These are Markov Decision Processes in parallel satisfying a condition first enunciated by Whittle. The theory of Gittins indices forms the basis of the analysis.
Distributed Computation for Linear Programming Problems Satisfying a Certain Diagonal Dominance Condition
Authors: Tseng Paul
Published: October 2008

A block-coordinate ascent method for a class of linear programming problems whose constraints satisfy a certain diagonal dominance condition is proposed. This method partitions the original linear program into subprograms where each subprogram corresponds uniquely to a subset of the decision variables of the problem. At each iteration, one of the subprograms is solved by adjusting its corresponding variables, while the other variables are held constant. The algorithmic mapping underlying this method is shown to be monotone and contractive. Using the contractive property, the method is shown to converge even when implemented in an asynchronous, distributed manner, and that its rate of convergence can be estimated from the synchronization parameter.
Existence and Uniqueness of Multi-Agent Equilibrium in a Stochastic, Dynamic Consumption/Investment Model
Authors: Karatzas Ioannis , Lehoczky John P. , Shreve Steven E.
Published: October 2008

We consider an economy in which a set of agents own productive assets which provide commodity dividend streams, and the agents also receive individual commodity income streams, over a finite time horizon. The agents can buy and sell the commodity at a certain spot price and buy and sell their shares of the productive assets. The proceeds can be invested in financial assets whose prices are modelled as semimartingales. Each agent's objective is to choose a commodity consumption process and to manage his portfolio so as to maximize the expected utility of his consumption, subject to having nonnegative wealth at the terminal time. We derive the optimal agent consumption and investment decision processes when the prices of the productive assets and commodity spot prices are specified. We prove the existence and uniqueness of an “equilibrium” commodity spot price process and productive asset prices. When the agents solve their individual optimization problems using the equilibrium prices, all of the commodity is exactly consumed as it is received, all of the productive assets are exactly owned and the financial markets are in zero net supply.
Optimal Control of a Two-Station Brownian Network
Authors: Wein Lawrence M.
Published: October 2008

Harrison [7] has introduced a model called a Brownian network, which approximates a multiclass queueing network with dynamic scheduling capability. In the present paper, a particular Brownian network control problem is considered that approximates a mathematically intractable scheduling problem for a two-station multiclass queueing network. A reformulation of the Brownian network control problem is solved. Linear programming is used to reduce the reformulated problem to a singular control problem for a one-dimensional Brownian motion. The objective of the singular control problem is to minimize the long-run expected average holding cost of the controlled process, subject to constraints on the long-run expected average amount of control exerted.