bluuebunny/crossref_metadata_2025 huggingface dataset:
Simple Power-of-Two Policies are Close to Optimal in a General Class of Production/Distribution Networks with General Joint Setup Costs
Authors: Federgruen A. , Queyranne M. , Zheng Yu-Sheng
Published: October 2008

We consider a production/distribution network represented by a general directed acyclic network. Each node is associated with a specific “product” or item at a given location and/or production stage. An arc (i, j) indicates that item i is used to “produce” item j. External demands may occur at any of the network's nodes. These demands occur continuously at item specific constant rates. Components may be assembled in any given proportions.

The cost structure consists of inventory carrying, and variable and fixed production/distribution costs. The latter depend, at any given replenishment epoch, on the specific set of items being replenished, according to an arbitrary set function merely assumed to be monotone and submodular.

We show that a simply structured, so-called power-of-two policy is guaranteed to come within 2% of a lower bound for the minimum cost. Under a power-of-two policy, all items are replenished at constant intervals and only when their inventory drops to zero; moreover, these replenishment intervals are all power-of-two multiples of a common base planning period. The above results generalize those of Roundy (1986).
Rates of Convergence for Quasi-Additive Smooth Euclidean Functionals and Application to Combinatorial Optimization Problems
Authors: Jaillet Patrick
Published: October 2008

Rates of convergence of limit theorems are established for a class of random processes called here quasi-additive smooth Euclidean functionals. Examples include the objective functions of the traveling salesman problem, the Steiner tree problem, the minimum spanning tree problem, the minimum weight matching problem, and a variant of the minimum spanning tree problem with power weighted edges.
The Traveling Salesman Problem with Distances One and Two
Authors: Papadimitriou Christos H. , Yannakakis Mihalis
Published: October 2008

We present a polynomial-time approximation algorithm with worst-case ratio 7/6 for the special case of the traveling salesman problem in which all distances are either one or two. We also show that this special case of the traveling salesman problem is MAX SNP-hard, and therefore it is unlikely that it has a polynomial-time approximation scheme.
A Polynomial Barrier Algorithm for Linearly Constrained Convex Programming Problems
Authors: Kortanek K. O. , Zhu Jishan
Published: October 2008

We consider the standard linearly constrained convex program min{f(x) ∣ x ∈ ℝn, Ax = b, x ≥ 0} where f(x) satisfies a certain scaled Lipschitz condition. Using the classical logarithmic barrier method our algorithm obtains an ε-solution within O(√n|ln ε|) or O(n|ln ε|) total iterations depending on the updating of the barrier parameter.
Stability Results for Ekeland's ε-Variational Principle and Cone Extremal Solutions
Authors: Attouch Hedy , Riahi Hassan
Published: October 2008

Given X a Banach space and f: X → ℝ ∪ {+∞} a proper lower semicontinuous function which is bounded from below, the Ekeland's ε-variational principle asserts the existence of a point x̄ in X, which we call ε-extremal with respect to f, which satisfies

f(u) > f(x̄) − ε‖u − x̄‖ for all u ∈ X, u ≠ x̄.

By using set convergence notions (Kuratowski-Painlevé, Mosco, bounded Hausdorff) and their epigraphical versions we study the (semi) continuity properties of the mapping which to f associates ε-ext f the set of such ε-extremal points. The key for the geometrical understanding of such properties is to consider the equivalent Phelps extremization principle which, given a closed set D in X and a partial ordering with respect to a pointed cone, associates the set of elements of D maximal with respect to this order. Direct or potential applications are given in various fields (multicriteria optimization, numerical algorithmic, calculus of variations).
An Approximation for a Continuous Max-Flow Problem
Authors: Blum Wolfgang
Published: October 2008

We consider an approximation for the continuous max-flow problem stated in [2] by a sequence of max-flow problems in finite networks. The used approximation scheme was introduced by Gomory and Hu in [6, Chapter 12]. But in [6] there is no definition of a continuous flow and therefore also no proof of a convergence of network flows to continuous flows. In this sense this paper solves the central open problem of Chapter 12 in [6].
Hit-and-Run Algorithms for Generating Multivariate Distributions
Authors: Bélisle Claude J. P. , Romeijn H. Edwin , Smith Robert L.
Published: October 2008

We introduce a general class of Hit-and-Run algorithms for generating essentially arbitrary absolutely continuous distributions on Rd. They include the Hypersphere Directions algorithm and the Coordinate Directions algorithm that have been proposed for identifying nonredundant linear constraints and for generating uniform distributions over subsets of Rd. Given a bounded open set S in Rd, an absolutely continuous probability distribution π on S (the target distribution) and an arbitrary probability distribution ν on the boundary of the d-dimensional unit sphere centered at the origin (the direction distribution), the (ν, π)-Hit-and-Run algorithm produces a sequence of iteration points as follows. Given the nth iteration point x, choose a direction θ according to the distribution ν and then choose the (n + 1)st iteration point according to the conditionalization of the distribution π along the line defined by x and x + θ. Under mild conditions, we show that this sequence of points is a Harris recurrent reversible Markov chain converging in total variation to the target distribution π.
A Lower Bound on the Expected Cost of an Optimal Assignment
Authors: Goemans Michel X. , Kodialam Muralidharan S.
Published: October 2008

We propose a dual heuristic for the assignment problem. We analyze this heuristic when the costs are independently and uniformly distributed between 0 and 1. As a result, we derive a lower bound on the expected cost of an optimal assignment, namely we show that it exceeds α − o(1), where α > 1.441.
Least Controls for a Class of Constrained Linear Stochastic Systems
Authors: Yang Ping
Published: October 2008

This paper introduces a class of constrained linear stochastic systems. The main objective is to investigate whether there exists a least control, in a sense that it exerts least effort in controlling the system to within a predetermined region. Our approach of finding a least control is: (a) to characterize a class of functional polyhedral sets of functions which have least elements, and (b) to construct a least-control process through these least elements. Existence of a least control is established. And the connection between a least control and a solution of the dynamic complementarity problem (DCP) is also discussed.
On the Stochastic Euclidean Travelling Salesperson Problem for Distributions with Unbounded Support
Authors: Rhee Wansoo T.
Published: October 2008

We study the asymptotic behavior of the shortest tour Tn through n points X1, …, Xn in ℝd (d ≥ 2), where (Xi)i≥1 are i.i.d. random variables, whose density f(x) has an unbounded support. Beardwood et al. [2] conjectured that Tn/n1−1/d converges a.s. if and only if ∫ f(x)1−1/d dx < ∞ and ∫ f(x)‖x‖d/(d−1) dx < ∞. We disprove this conjecture, and we show that the second integrability condition is not strong enough. We give a stronger condition that is optimal (but not necessary).
Convergence Properties of Iterative Methods for Symmetric Positive Semidefinite Linear Complementarity Problems
Authors: De Pierro Alvaro R. , Iusem Alfredo N.
Published: October 2008

We consider iterative methods using splittings for solving symmetric positive semidefinite linear complementarity problems. We prove strong convergence, i.e., convergence of the whole sequence, for these types of methods with the only hypothesis of existence of a solution. To do this we introduce dual methods for solving a dual quadratic programming problem and we prove linear convergence of such methods.
Closure Properties of Independence Concepts for Continuous Utilities
Authors: von Stengel Bernhard
Published: October 2008

This paper examines nine independence concepts for ordinal and expected utilities: utility and preference independence, weak separability (a uniqueness of nonstrict conditional preferences), as well as generalizations that allow for complete indifference or reversal of preferences. Some of these conditions are closed under set-theoretic operations, which simplifies the verification of such assumptions in a practical decision analysis. Preference independence is closed under union without assumptions of strict essentiality, which are however necessary for closure under differences of preference independence and its mentioned generalizations. The well-known additive representation of a utility function is used, in a corrected form with a self-contained proof, to show closure under symmetric difference. This generalizes a classical result of Gorman (1968), and supplements its proof. Generalized utility independence has all, whereas weak separability has no closure properties. An independent set of any kind is utility or preference independent if this holds for a subset. Counterexamples are given throughout to show that the results are as strong as possible. The approach consistently uses conditional functions instead of preference relations, based on simple topological notions like connectivity and continuity.
Quasi-Stationary Distributions of Single-Server Phase-Type Queues
Authors: Kijima Masaaki
Published: October 2008

Let Q̃ be the infinitesimal generator governing a PH/PH/1 queueing process and let Q be the lossy generator obtained by deleting the states corresponding to no customers in the queue. In this paper, after uniformization P = I + Q/ν for sufficiently large ν where I denotes the identity matrix, we study the quasi-stationary distribution of the lossy Markov chain in discrete time governed by P. The convergence norm r of P, i.e., r = R−1 and R = sup{z· ∑k=0∞ Pk zk < ∞}, which is of independent interest, is determined and P is shown to be R-transient. It is proved that if the traffic intensity is strictly less than 1 then the quasi-stationary distribution x, from which the quasi-stationary queue length and virtual waiting time distributions of the phase-type queue can be determined, exists and is a unique solution to the system rxT = xTP (T denotes the transpose). Finally, we demonstrate that results for M/PH/1 and PH/M/1 queues obtained in Kyprianou (1971, 1972) for more slightly general settings are easily derived by our method.
On Line Bin Packing with Items of Random Size
Authors: Rhee Wansoo T. , Talagrand Michel
Published: October 2008

Consider an i.i.d. sequence of random variables X1, …, Xn distributed according to a given distribution μ on [0, 1]. Let c(μ) be the asymptotic optimal packing ratio, i.e., c(μ) = limn→∞ETn/n, where Tn is the minimum number of unit size bins needed to pack X1, …, Xn. We prove the existence of an on line algorithm, dependent on μ, that packs X1, …, Xn in nc(μ) + O(n1/2(log n)3/4) bins.
Transform-Free Analysis of M/G/1/K and Related Queues
Authors: Niu Shun-Chen , Cooper Robert B.
Published: October 2008

Using constructive, sample-path arguments, we derive a variety of transform-free results about queue lengths and waiting times for the M/G/1/K queue. In classical analyses of M/G/1/K, it is typical to work with Markov processes obtained by defining the “state” of the system at a time epoch to be the number of customers present and, as supplementary information, the remaining service time of the customer, if any, in service. In contrast, the key idea behind our analysis is to work with a modified Markov process that has a more-detailed state description. At any time epoch t when the server is busy, we replace “the number of customers present” by two variables, namely (a) the number of customers who where (and still are) waiting in the queue immediately after the start of the service in progress, and (b) the number of customers who arrived during that same service but prior to t. We show that this minor change of state definition, coupled with a rigorous formalization of the intuitive notion of a “test customer” (whose viewpoint is adopted in our analysis of the modified Markov process) makes possible a surprisingly simple analysis of the M/G/1/K queue. We also show that our method can be extended easily to yield similar results for various generalizations of the basic M/G/1/K model.
The Frobenius Problem and Maximal Lattice Free Bodies
Authors: Scarf Herbert E. , Shallcross David F.
Published: October 2008

Let p = (p1, …, pn) be a vector of positive integers whose greatest common divisor is unity. The Frobenius problem is to find the largest integer f* which cannot be written as a nonnegative integral combination of the pi. In this note we relate the Frobenius problem to the topic of maximal lattice free bodies and describe an algorithm for n = 3.
A Bound on the Proportion of Pure Strategy Equilibria in Generic Games
Authors: Gül Faruk , Pearce David , Stacchetti Ennio
Published: October 2008

In a generic finite normal form game with 2α + 1 Nash equilibria, at least α of the equilibria are nondegenerate mixed strategy equilibria (that is, they involve randomization by some players).
The Complexity of Eliminating Dominated Strategies
Authors: Gilboa Itzhak , Kalai Ehud , Zemel Eitan
Published: October 2008

This paper deals with the computational complexity of some yes/no problems associated with sequential elimination of strategies using three domination relations: strong domination (strict inequalities), weak domination (weak inequalities), and domination (the asymmetric part of weak domination). Classification of various problems as polynomial or NP-complete seems to suggest that strong domination is a simple notion, whereas weak domination and domination are complicated ones.
Random Walk and the Area Below its Path
Authors: Harel Arie
Published: October 2008

A simple random walk with reflected origin is considered. The walk starts at the origin and it must return to the origin at time 2n. We show that the expected area below the path of this walk is n22n−1/Cn2n. If, however, the walk is required to return to the origin for the first time at time 2n, then the expected area below the path of this Bernoulli excursion is (2n − 1)22n−1/Cn2n.

We also show that if V1 < ⋯ < Vn is the order statistics based on a sample of size n from a uniform distribution over (0, 1), and that if U1 < ⋯ < Un is another independent set of order statistics from the same distribution, then

E [∑i=1n |Vi − Ui|] = n22n−1/[(2n + 1)Cn2n]

We use this result to find an average-case performance of the Earliest Due Date (EDD) heuristic for one machine scheduling problem with earliness and tardiness penalties. We also apply some of the results to Larson's Queue Inference Engine (1990).
Continuity Properties of Expectation Functions in Stochastic Integer Programming
Authors: Schultz Rüdiger
Published: October 2008

Sufficient conditions for the (Lipschitz) continuity of the expectation of second-stage costs are given for two-stage stochastic programs, where the optimization problem in the second stage is a mixed-integer linear program. We also present counterexamples to show that, in general, the results can no longer be maintained when relaxing assumptions as well as multivariate probability distributions for which the theory works.
Inequalities for Bin Packing—II
Authors: Rhee Wansoo T.
Published: October 2008

Consider the minimum number Bn of unit size bins needed to pack items X1, …, Xn that are independently distributed according to a given distribution μ concentrated on [0, 1]. We establish a sharp inequality for the deviation of Bn from its expectation.
Adaptive Lexicographic Optimization in Multi-Class M/GI/1 Queues
Authors: Bhattacharya P. P. , Georgiadis L. , Tsoucas P. , Viniotis I.
Published: October 2008

We consider a multi-class M/GI/1 system, in which an average response time objective is associated with each class. The performance of each class is measured by the ratio of the average response time over the corresponding value of the objective. To achieve fairness in service allocation it is required to find a policy that lexicographically minimizes the vector of performance ratios arranged in nonincreasing order. We provide such a policy that is adaptive, uses only knowledge of arrival and departure instants, and is thus easy to implement. We also consider a variant of this policy which adapts faster to changes in the statistical parameters of the model. Both policies are analyzed via associated stochastic recursions using techniques of stochastic approximation.
Stable Matchings, Optimal Assignments, and Linear Programming
Authors: Roth Alvin E. , Rothblum Uriel G. , Vande Vate John H.
Published: October 2008

Vande Vate (1989) described the polytope whose extreme points are the stable (core) matchings in the Marriage Problem. Rothblum (1989) simplified and extended this result. This paper explores a corresponding linear program, its dual and consequences of the fact that the dual solutions have an unusually direct relation to the primal solutions. This close relationship allows us to provide simple proofs both of Vande Vate and Rothblum's results and of other important results about the core of marriage markets. These proofs help explain the structure shared by the marriage problem (without sidepayments) and the assignment game (with sidepayments). The paper further explores “fractional” matchings, which may be interpreted as lotteries over possible matches or as time-sharing arrangements. We show that those fractional matchings in the Stable Marriage Polytope form a lattice with respect to a partial ordering that involves stochastic dominance. Thus, all expected utility functions corresponding to the same ordinal preferences will agree on the relevant comparisons. Finally, we provide linear programming proofs of slightly stronger versions of known incentive compatibility results.
Asymptotic Behavior of Optimal Solutions in Stochastic Programming
Authors: Shapiro Alexander
Published: October 2008

Asymptotic behavior of optimal solutions x̂n of a sequence of stochastic programming problems is studied. Variational and generalized equations approaches are discussed. An expansion of x̂n in terms of a parametrized mathematical programming problem, depending on a single random vector, is given. When optimal solutions of the parametrized program are directionally differentiable, this expansion leads to a close form expression for the asymptotic distribution of x̂n. Applicability of the involved regularity conditions to nondifferentiable cases, and in particular to stochastic programming with recourse, is discussed.
Asymptotically Optimal Loss Network Control
Authors: Hunt P. J. , Laws C. N.
Published: October 2008

We consider a loss network which employs alternative routing and derive the asymptotically optimal call acceptance and routing policy, the limit being as the number of links becomes large. We show that a well known control policy, least busy alternative routing with trunk reservation, is asymptotically optimal. The approach of the paper is not specific to the loss network control problem that we consider but is applicable more generally. The results are obtained by combining weak convergence with linear programming techniques.
Lyapounov Functions for Jackson Networks
Authors: Fayolle G. , Malyshev V. A. , Menshikov M. V. , Sidorenko A. F.
Published: October 2008

We construct explicitly Lyapounov functions for Markovian Jackson networks. Two direct corollaries are obtained: first a proof of the necessary and sufficient conditions for ergodicity, without using the famous Jackson's product form; secondly, an exponential convergence rate to the stationary distribution. We also consider small perturbations of the transition probabilities (yielding thus non-Jackson networks) and prove that the corresponding stationary distribution is an analytic function of these perturbations.
Semiregularity and Generalized Subdifferentials with Applications to Optimization
Authors: Birge John R. , Qi Liqun
Published: October 2008

The Michel-Penot subdifferential of a locally Lipschitzian function is the principal part of the Clarke subdifferential. It coincides with the G-derivative at differentiable points. A locally Lipschitzian function can be determined by its Michel-Penot subdifferential uniquely up to an additive constant, though this cannot be done by its Clarke subdifferential if the set of abnormal points is not negligible. A set-valued operator is the Michel-Penot subdifferential of a locally Lipschitzian function if and only if it is a seminormal operator satisfying a cyclical condition. Various calculus rules hold for the Michel-Penot subdifferential. Equalities hold for these rules at a point under semiregularity, which is weaker than regularity. For a locally Lipschitzian function in a separable Banach space, semiregularity holds everywhere except for a Haar zero set. Applications in optimization are discussed.
On Harris Recurrence in Continuous Time
Authors: Kaspi Haya , Mandelbaum Avi
Published: October 2008

We show that a continuous-time Markov process X is Harris recurrent if and only if there exists a nonzero α-finite measure ν on its state space such that X surely hits sets with positive ν-measure. This simple criterion is applied to some nonparametric closed queueing networks.
Hamiltonian Cycles and Markov Chains
Authors: Filar Jerzy A. , Krass Dmitry
Published: October 2008

In this paper we derive new characterizations of the Hamiltonian cycles of a directed graph, and a new LP-relaxation of the Traveling Salesman Problem. Our results are obtained via an embedding of these combinatorial optimization problems in suitably perturbed controlled Markov chains. This embedding lends probabilistic interpretation to many of the quantities of interest, which in turn lead naturally to the introduction of a quadratic entropy-like function.
Toward Probabilistic Analysis of Interior-Point Algorithms for Linear Programming
Authors: Ye Yinyu
Published: October 2008

We propose an approach based on interior-point algorithms for linear programming (LP). We show that the algorithm solves a class of LP problems in strongly polynomial time, O(√n log n)-iteration, where each iteration solves a system of linear equations with n variables. The recent statistical data of the solutions of the NETLIB LP problems seem to indicate that virtually all of these problems are in this class. Then, we show that some random LP problems, with high probability (probability converges to one as n approaches infinity), are in this class. These random LP problems include recent Todd's probabilistic models with the standard Gauss distribution.
Unstable Asymptotics for Nonstationary Queues
Authors: Massey William A. , Whitt Ward
Published: October 2008

We relate laws of large numbers and central limit theorems for nonstationary counting processes to corresponding limits for their inverse processes. We apply these results to develop approximations for queues that are unstable in a nonstationary manner. We obtain unstable nonstationary analogs of the queueing relation L = λ W and associated central-limit- theorem versions. For modeling and to obtain the first limits, we can construct nonstationary point processes as random time-transformations of familiar point processes, such as renewal processes and stationary point processes. We deduce the asymptotic behavior of the nonstationary point process from the asymptotic behavior of the familiar point process and the time transformation.
Bounds for Two-Stage Stochastic Programs with Fixed Recourse
Authors: Edirisinghe N. C. P. , Ziemba W. T.
Published: October 2008

This paper develops upper and lower bounds on two-stage stochastic linear programs using limited moment information. The case considered is when both the right-hand side as well as the objective coefficients of the second stage problem are random. Random variables are allowed to have arbitrary multivariate probability distributions with bounded support. First, upper and lower bounds are obtained using first and cross moments, from which we develop bounds using only first moments. The bounds are shown to solve the respective general moment problems.
Bounding the Expectation of a Saddle Function with Application to Stochastic Programming
Authors: Edirisinghe N. C. P. , Ziemba W. T.
Published: October 2008

We previously obtained tight upper and lower bounds to the expectation of a saddle function of multivariate random variables using first and cross moments of the random variables without independence assumptions. These bounds are applicable when domains of the random vectors are compact sets in the euclidean space. In this paper, we extend the results to the case of unbounded domains, similar in spirit to the extensions by Birge and Wets in the pure convex case. The relationship of these bounds to a certain generalized moment problem is also investigated. Finally, for solving stochastic linear programs utilizing the above bounding procedures, a computationally more appealing order-cone decomposition scheme is proposed which behaves quadratically in the number of random variables. Moreover, the resulting upper and lower approximations are amenable to efficient solution techniques.
Global Convergence of Damped Newton's Method for Nonsmooth Equations via the Path Search
Authors: Ralph Daniel
Published: October 2008

A natural damping of Newton's method for nonsmooth equations is presented. This damping, via the path search instead of the traditional line search, enlarges the domain of convergence of Newton's method and therefore is said to be globally convergent. Convergence behavior is like that of line search damped Newton's method for smooth equations, including Q-quadratic convergence rates under appropriate conditions.

Applications of the path search include damping Robinson-Newton's method for nonsmooth normal equations corresponding to nonlinear complementarity problems and variational inequalities, hence damping both Wilson's method (sequential quadratic programming) for nonlinear programming and Josephy-Newton's method for generalized equations. Computational examples from nonlinear programming are given.
On Multiple Choice Secretary Problems
Authors: Preater J.
Published: October 2008

Two secretary problems based on relative rank are considered, in which the decision maker has any fixed number of choices. In the first the payoff depends in an arbitrary way on acquisitions of ranks 1 and 2; in the second the aim is to maximise the probability of obtaining the best 3 objects. In each case the existence of an optimal selection policy of time threshold type is established.
The Linear Complementarity Problem with Exact Order Matrices
Authors: Mohan S. R. , Parthasarathy T. , Sridhar R.
Published: October 2008

(Dedicated to Professor K. G. Ramamurthy on the occasion of his 60th birthday.)

A real n by n matrix A is called an N(P)-matrix of exact order k if the principal minors of A of order 1 through (n + k) are negative (positive) and (n − k + 1) through n are positive (negative). In this paper the properties of exact order 1 and 2 matrices are investigated, using the linear complementarity problem LCP(q, A) for each q ∈ Rn. A complete characterization of the class of exact order 1 based on the number of solutions to the LCP(q, A) for each q ∈ Rn is presented. In the last season we consider the problem of computing a solution to the LCP(q, A) when A is a matrix of exact order 1 or 2.
Parallel Constraint Distribution in Convex Quadratic Programming
Authors: Ferris Michael C.
Published: October 2008

We consider convex quadratic programs with large numbers of constraints. We distribute these constraints among several parallel processors and modify the objective function for each of these subproblems with Lagrange multiplier information from the other processors. New Lagrange multiplier information is aggregated in a master processor and the whole process is repeated Linear convergence is established for strongly convex quadratic programs by formulating the algorithm in an appropriate dual space. The algorithm corresponds to a step of an iterative matrix splitting algorithm for a symmetric linear complementarity problem followed by a projection onto a subspace.
Derivatives with Support and Applications
Authors: Luc Dinh The , Théra Michel
Published: October 2008

A new concept of derivative is introduced reflecting the global, rather than the local, behavior of a given function. Basic properties and calculus rules for this derivative are provided. Then they are applied to establish some characterizations of convex functions and some optimality conditions in mathematical programming.
Optimality Conditions for Control Problems Governed by Variational Inequalities
Authors: Ndoutoume James Louis
Published: October 2008

This paper deals with the theory of first-order necessary conditions of optimality for nonsmooth control problems governed by variational inequalities. We present a general approach in which necessary conditions of first-order are obtained by means of differentiation tools based on epi-convergence of second-order differential quotients.
Discounted Replacement, Maintenance, and Repair Problems in Reliability
Authors: Anderson Robert F.
Published: October 2008

Three related stochastic control problems from reliability theory referred to as the optimal replacement, the optimal maintenance-replacement and the optimal maintenance-repair problems are considered in the context of a nondecreasing Markov wear process x(t): t ≥ 0 with an independent random threshold failure mechanism. Each is considered in continuous time and in the discounted case. Let Y be the random threshold and σ = inf{x(t) ≥ Y} be the time of failure. For the replacement problem, at any time before failure a decision can be made to replace the current device by a new one at cost c(x(t)). At failure the failed device is immediately replaced by a new one at cost d(x(σ)). The maintenance-replacement problem has the same constraints at failure as the replacement problem, but at any time before failure a decision can be made to maintain the current device to any lower wear state y at cost c(x(t), y). For the maintenance-repair problem, before failure a decision to perform maintenance as in the maintenance-replacement problem can be made, while at failure instead of replacing immediately by a new device, repair to any lower wear state y is considered at cost d(x(σ), y). Additionally for each of the problems a cost per unit time f(x(t)) is also considered. The methods of quasi-variational inequalities and impulse control are used to analyze the problems. The main technical point is to generalize the usual variational formulation of the value function of an optimal stopping problem so as to allow consideration of x(σ) dependent cost structures.
On the Invariance Principle for the First Passage Time
Authors: Puhalskii A.
Published: October 2008

New results are obtained on the connection between the invariance principle for the first passage time process and that for the underlying processes. The main contribution is that the ‘passing’ process may have general drift. An example of the application is given which shows that this is of use in deriving limit theorems for delays from limit theorems for queue lengths when studying queueing systems with queue-dependent arrival or (and) service completion rates.
Construction of Stationary Markov Equilibria in a Strategic Market Game
Authors: Karatzas Ioannis , Shubik Martin , Sudderth William D.
Published: October 2008

This paper studies stationary noncooperative equilibria in an economy with fiat money, one nondurable commodity, countably many time-periods, no credit or futures market, and a measure space of agents—who may differ in their preferences and in the distributions of their (random) endowments. These agents are immortal, and hold fiat money as a means of hedging against the random fluctuations in their endowments of the commodity. In the aggregate, these fluctuations offset each other, and equilibrium prices are constant.

We carry out an equilibrium analysis that focuses on distribution of wealth, on consumption, and on price formation. A careful analysis of the one-agent, infinite-horizon optimization problem, and of the invariant measure for the associated optimally controlled Markov chain, leads by aggregation to a stationary noncooperative or competitive equilibrium. This consists of a price for the commodity and of a distribution of wealth across agents which, under appropriate simple strategies for the agents, stay fixed from period to period and preserve the basic quantities of the model.

We hope that, in future work, we shall be able to address additional features of the model treated here, such as borrowing and lending at appropriate (endogenously determined) interest rates, the endogenous production of commodity, overlapping generations of agents, and bankruptcy and treatment of creditors.
Some Stochastic Bounds for Dams and Queues
Authors: Harrison J. Michael
Published: October 2008

Let X = {X(t), t > 0} be a process of the form X(t) = Z(t) − ct, where c is a positive constant and Z is an infinitely divisible, nondecreasing pure jump process. Assuming E[X(t)] < 0. let U be the d.f. of M = sup X(t). As is well known, U is the contents distribution of a dam with input Z and release rate c. If Z is compound Poisson, one can alternately view U as the waiting time distribution for an M/G/1 queue or 1 − U as the ruin function for a risk process.

Letting X and X0 be two processes of the indicated form, it is shown that U ≤ U0 if the two jump measures are ordered in a sense weaker than stochastic dominance. In the case where E(M) = E(M0), a different condition on the jump measures yields E[f(M)] ≤ E[f(M0)] for all concave f, this resulting from second-order stochastic dominance of the supremum distributions. By way of application, processes with deterministic jumps are shown to be extremal in certain ways, and those with exponential jumps are shown to be extremal among the class having IFR jump distribution. Finally, an extremal property of Brownian Motion (which is not among the class of processes considered) is demonstrated, this yielding simple bounds for E[f(M)] with f concave or convex. It is shown how all the bounds obtained for U or E[f(M)] can be further sharpened with additional computation.
Individual Rationality and Nash's Solution to the Bargaining Problem
Authors: Roth Alvin E.
Published: October 2008

The axiom of Pareto optimally in Nash's definition of a solution to the bargaining problem may be replaced by an axiom of individual rationality, without altering the result.
Persistently ϵ-Optimal Strategies
Authors: Dubins Lester E. , Sudderth William D.
Published: October 2008

There are strategies available for nonnegative gambling problems which are not only ϵ-optimal but persist in being conditionally ϵ-optimal along every history.
Analysis of the Earliest Due Date Scheduling Rule in Queueing Systems
Authors: Goldberg Henry M.
Published: October 2008

We investigate a model for a general single server queueing system operating under the earliest due date scheduling rule, which can be interpreted more generally as a dynamic priority queue-discipline. We consider both preemptive resume and non preemptive disciplines within this framework. No assumptions are made about the distributions of interarrival times and service times of customers in this model, so that characterizations can be derived for arbitrary systems. The analysis depends on suitably defining the concepts of the server's workload and busy period of the system with respect to the priority classes involved. Equations are developed for the virtual waiting times of customers arriving at the system at any time t, and these imply properties of virtual lateness. In the case of an M/G/1 system, expressions for mean waiting times in transient and steady state are derived, and these are found to be analogous to the expressions derived by Cobham in the special case of static priorities. Bounds for expected waiting lime and lateness are obtained, and the increased flexibility of optimization with respect to dynamic priorities is indicated. The results in the paper extend to the case of a number of servers in parallel instead of a single server.
An Algorithm for Constrained Optimization with Semismooth Functions
Authors: Mifflin Robert
Published: October 2008

We present an implementable algorithm for solving constrained optmization problems defined by functions that are not everywhere differenliable. The method is based on combining, modifying and extending the nonsmooth optimization work of Wolfe, Leraarechal, Feuer, Poljak and Merrill. It can be thought of as a generalized reset conjugate gradient algorithm.

We also introduce the class of weakly upper semismooth functions. These functions are locally Lipschitz and have a semicontinuous relationship between their generalized gradient sets and their directional derivatives. The algorithm is shown to converge to stationary points of the optimization problem if the objective and constraint functions are weakly upper semismooth. Such points are optimal points if the problem functions are also semiconvex and a constraint qualification is satisfied. Under stronger convexity assumptions, bounds on the deviation from optimally of the algorithm iterates are given.
A Substitute Inverse for the Basis of a Staircase Structure Linear Program
Authors: Wollmer Richard D.
Published: October 2008

The constraints of a staircase structure linear program are of the following form: A1x1 = d1; Bt−1 + Atxt = dt (t = 2, …, T). Letting mi be the number of constraints m period i the substitute inverse consists of the inverse of T matrices which are mi × mi = 1, …, T, as opposed to the actual inverse which is m × m, m = ∑mi. Updating the substitute inverse consists of updating some, but not necessarily all, of the T inverses. This may be done by appending one or more columns and pivoting on them or by adding a dyad matrix. Applications to the PILOT energy model will be discussed.
An Upper Bound for the Equilibrium Mean Wait in a Stationary GI/G/1 Queue
Authors: Calo S. B. , Schwartz S. C.
Published: October 2008

Various bounds have been proposed for the mean value of the equilibrium waiting time random variable, E{W}, in a stationary GI/G/1 queueing system. In this note we establish a new upper bound which is derived using a convexity argument similar to that of Marshall (Marshall, K. T. 1968. Some inequalities in queueing. Oper. Res. 16 651–665.) but applied to an algebraic expression for E{W} previously used by Kingman (Kingman, J. F. C. 1962. Some inequalities for the queue GI/G/1. Biometrika 49 315–324.), This bound and others have been compared numerically in a variety of systems; two graphs are presented to illustrate the results of such computations.
Unconstrained Optimization by Approximation of the Gradient Path
Authors: Vial Jean-Philippe , Zang Israel
Published: October 2008

A gradient-path oriented algorithm for unconstrained minimization, requiring first derivatives of the objective, is presented. The algorithm possesses the quadratic termination property and it is shown to converge to a stationary point of a continuously differentiable Function.
Nonconvex Duality in Multiobjective Optimization
Authors: Di Guglielmo F
Published: October 2008

Nonconvex duality properties for multiobjective optimization problems are obtained by using a characterization of Pareto optima by means of generalized Tchebycheff norms.

Bounds for the corresponding duality gap are given, and approximate Pareto multipliers are constructed. A generalized notion of Pareto multipliers for quasi-convex multiobjective problems is introduced.
The Probability that a Random Polytope is Bounded
Authors: Schmidt Brian K. , Mattheiss T. H.
Published: October 2008

A formula for the probability that a randomly generated n-polytope defined by m half-spaces is bounded is presented. Results of a simulation giving (i) the probability that all m constraints are relevant and (ii) a formula for the expected number of vertices of a polytope, are presented.
On Level Crossings and Cycles in Dam Processes
Authors: Cohen J. W. , Rubinovitch Michael
Published: October 2008

The classical dam with input according to a process with stationary, independent increments and output at unit rate is considered. The stochastic properties of level crossings, i.e. up- and downcrossings of a fixed level x > 0 are studied. It is shown that successive downcrossings of any such level constitute a renewal process with a.s. strictly positive lifetimes. This property allows the content process to be described as a regenerative process. In fact several types of imbedded renewal processes may be defined and various cycles in the content process may be identified. The number of downcrossings of a fixed level in each such cycle as well as other functionals are studied. In particular, some new properties of the zero set of the dam process are obtained. This study has arisen from questions in cost optimization problems of dams and a simple example is discussed to illustrate the use of the results in this context.
The Duality between Suboptimization and Parameter Deletion
Authors: Peterson Elmor L.
Published: October 2008

The main tool used in studying the influence of given perturbation parameters on a given optimization problem is, of course, the corresponding Rockafellar dual problem (in which the dual variables are in a one-to-one correspondence with the parameters). However, even when the given optimization problem is defined in terms of simple formulas, there are many important cases where the corresponding dual problem cannot be computed explicitly (in terms of simple formulas) unless certain additional (uninteresting) perturbation parameters are included. Under a very weak hypothesis, the main theorem to be given here asserts that a (sub)optimization of the resulting dual problem over the additional (uninteresting) dual variables produces the desired dual problem (i.e., the dual problem that corresponds to the original optimization problem without the additional perturbation parameters). In addition to its uses in parametric analysis this theorem can be used to show that various decomposition principles are dual to one another and hence are essentially equivalent.
An Eccentric Barycentric fixed Point Algorithm
Authors: Zangwill Willard I.
Published: October 2008

One of the newest areas of mathematical programming, the calculation of fixed points, permits solution of problems unsolvable by earlier methods. The algorithm of this paper, moreover, details two theoretical improvements over previous fixed point algorithms. First, previous algorithms utilize a homotopy structure in which an additional dimension is added to the original problem. This algorithm eliminates the “additional dimension,” thereby simplifying the analysis and easing understanding. Second, previous algorithms require the points generated to conform to a fixed predetermined grid. This algorithm, however, allows the points to be selected flexibly dependent upon the actual function values encountered. The algorithm is therefore adaptive. Hopefully, this adaptive feature will speed convergence. It also suggests a new area of research, that of determining “optimum” adaption functions. To achieve all this, the algorithm utilizes an unconventional modification of the barycentric subdivision in which the points may be selected “off center” (hence the name eccentric). Finally, the algorithm corrects an erroneous procedure often “discovered” by new students, and since it builds from that, this paper may thus also serve as a useful introduction to the field for students.
A Surface of Analytic Centers and Primal-Dual Infeasible-Interior-Point Algorithms for Linear Programming
Authors: Mizuno Shinji , Todd Michael J. , Ye Yinyu
Published: October 2008

We define a surface of analytic centers determined by a primal-dual pair of linear programming problems and an infeasible interior point. Then we study the boundary of the surface by analyzing limiting behavior of paths on the surface and sequences in a neighborhood of the surface. We introduce generic primal-dual infeasible-interior-point algorithms in which the search direction is the Newton direction for a system defining a point on the surface. We show that feasible-interior-point algorithms for artificial self-dual problems and for an artificial primal-dual pair of linear programming problems can he considered as special cases of these infeasible-interior-point algorithms or simple variants of them. In this sense, there are O(√nL)-iteration primal-dual infeasible-interior-point algorithms for linear programming.
Martingale Analysis for Assets with Discontinuous Returns
Authors: Bardhan Indrajit , Chao Xiuli
Published: October 2008

The equivalent martingale measure approach is applied to a financial market subject to jump-diffusion uncertainty. The uncertainty in the market is caused by a multidimensional Brownian motion process and a multidimensional point process of jumps admitting stochastic intensity. Under a boundedness condition on the relative risk premium on jumps, an equivalent risk-neutral probability measure is identified and is used to construct hedging portfolios for consumption processes and contingent claims. These are then applied to problems of utility maximization.
On the Value of Adaptive Solutions to Stochastic Scheduling Problems
Authors: Glazebrook K. D. , Owen R. W.
Published: October 2008

Two possible ways of dealing with the presence of unknown system parameters in a stochastic scheduling problem are (i) to give the unknowns prior distributions and implement a Bayes (adaptive) policy and (ii) to choose plausible values for the unknown parameters at the outset, thereafter treating them as known. Since adaptive policies are often difficult to construct and/or apply, route (ii) may be favoured if there is little to be lost by it. Hence we seek to quantify the value of an adaptive solution (VAS). For quite general classes of stochastic scheduling problems, both preemptive and nonpreemptive, we are able to relate the VAS to natural measures of the degree of peakedness of the prior distributions and the sensitivity of optimal policies to changes in value of the unknown parameters.
Fluid and Diffusion Approximations of a Two-Station Mixed Queueing Network
Authors: Nguyen Viên
Published: October 2008

The subject of this paper is a two-station mixed queueing network with two customer types: “Open” customers enter the network at station 1 and depart the system after receiving service. Meanwhile, a fixed number of “closed” customers circulate between stations 1 and 2. Such a mixed queueing network model can represent a single-stage production system that services both make-to-order and make-to-stock customers. We present fluid and diffusion limits for this network under the first-in-first-out service discipline. We find that the heavy traffic limit of the workload process at station 1 is a reflected Brownian motion (RBM) on a finite interval. This result is in contrast to the behavior of the original mixed network model, in which the workload at station 1 need not be bounded.
Problems of Adaptive Optimization In Multiclass M/GI/1 Queues with Bernoulli Feedback
Authors: Bhattacharya Partha P. , Georgiadis Leonidas , Tsoucas Pantelis
Published: October 2008

Adaptive algorithms are obtained for the solution of separable optimization problems in multiclass M/GI/1 queues with Bernoulli feedback. Optimality of the algorithms is established by modifying and extending methods of stochastic approximation. These algorithms, can be used as a basis for designing policies for semi-separable and approximate lexicographic optimization problems and in the case of M/GI/1 queues without feedback, they also provide a simple policy for lexicographic optimization. The results obtained on stochastic approximation imply convergence of classical recursions such as Robbins-Monroe in cases where the conditional second moment of their increments is not finite.