bluuebunny/crossref_metadata_2025 huggingface dataset:
Comparing Semi-Markov Processes
Authors: Sonderman David
Published: October 2008

Sufficient conditions are found for two semi-Markov processes to be stochastically ordered, i.e., for which two new semi-Markov processes can be constructed on a common probability space so that the new processes individually have the same distributions as the original processes and every sample path of the first new process lies below the corresponding sample path of the second new process. This ordering has recently been shown by Kamae, Krengel, and O’Brien (Kamae, T., V. Krengel, G. L. O’Brien. 1977. Stochastic inequalities on partially ordered spaces. Ann. Probab. 5 899–912.) to be equivalent to the definition of stochastic order usually seen in the literature; see Veinott (Veinott, A. F. Jr. 1965. Optimal policy in a dynamic, single product, nonstationary inventory model with several demand classes. Oper. Res. 13 761–778.). The conditions are: (i) the initial distribution of the first process is stochastically smaller than that of the second; (ii) for each ordered triple of states j ≤ k ≤ 1 and (unordered) holding times s and t, the instantaneous transition rate of the first process from j to the set of states exceeding 1 given its holding time in j is s is not less than the corresponding transition rate of the second process where j and s are replaced by k and t respectively; and (iii) the dual of condition (ii) obtained by reversing the order of the states. The construction is accomplished for semi-Markov processes for which all subprobability transition rates are absolutely continuous with failure rates uniformly bounded over finite intervals by representing the two semi-Markov processes as compositions of discrete-time stochastic processes with a sequence of Poisson processes. This permits application of recent comparison results for discrete-time stochastic processes by O'Brien (O'Brien, G. L. 1975a. The comparison method for stochastic processes. Ann. Probab. 3 80–88; O'Brien, G. L. 1975b. Inequalities for queues with dependent interarrival and service times. J. Appl. Probab. 12 653–656.).
Conditions for Convexity of Quasiconvex Functions
Authors: Crouzeix J. P.
Published: October 2008

Necessary and sufficient conditions for convexity of lower semi-continuous quasiconvex functions are given. By applying these results to positively homogeneous functions it is shown that if f is a quadratic form which is quasiconvex on a convex C then f is convexifiable, that is, there exists a strictly increasing function k such that k ∘ f is convex.
Optimal Stopping with a Horizon Constraint
Authors: Nachman David C.
Published: October 2008

A Langrangean function approach to optimality and duality is used to study the optimal stopping problem with a horizon constraint. This approach forces the analysis of the problem to “look beyond” the horizon time, which is essential to any implicit valuation of the horizon constraint. The results of this approach include the usual relationships between solutions to the primal and dual problems, optimality conditions, and saddlepoints of the Lagrangean function, as well as necessary optimality and strong duality theorems under a stability hypothesis. The constrained stopping problem is analogous in its simplicity to classical single equation constrained optimization in that an optimal multiplier is easily identified.
Probabilistic Analysis of the Planar k-Median Problem
Authors: Fisher M. L. , Hochbaum D. S.
Published: October 2008

We consider a problem in which we are given n points distributed randomly in a planar region of area A. We are asked to select K of the points to serve as centers so as to minimise the sum over the n points of the distance between each point and its closest center. This paper shows that the optimal value of this problem grows as [Formula: see text] almost everywhere.

This result is used to study an aggregation heuristic that is a formalized version of aggregation methods frequently used for practical location problems. Given any prespecified ϵ > 0, the heuristic can be made to achieve ϵ-optimality almost everywhere. The running time is polynomial in n if K ≤ ln n and linear in n if K ≤ ln ln n. Since all previously proposed heuristics: require n2 time even if K = 1, the aggregation heuristic is dominant for problems with sufficiently small K.

Although our main results are asymptotic for large n, the probability that they hold for finite n is known to exceed 1 − 2π−1/2(n − K)−2, which is nearly 1 even for moderate n − K.
Extreme Points of the Class of Discrete Decreasing Failure Rate Life Distributions
Authors: Langberg Naftali A. , León Ramón V. , Lynch James , Proschan Frank
Published: October 2008

We show that the class of discrete decreasing failure rate (DFR) life distributions is a convex class. We then obtain the extreme points of this class. Finally we show how to represent any discrete DFR distribution as a mixture of these extreme points.
Asymptotic Value of Mixed Games
Authors: Fogelman Francoise , Quinzii Martine
Published: October 2008

In this paper we are concerned with mixed games, i.e., games with on one hand an “ocean” of insignificant players (formalized by a continuum of players) and on the other hand some significant players (atoms). Considering these games as limits of finite games, we show, for the subset pFL, that the Shapley-Hart value of the mixed game corresponding to the uniform probability measure is the limit of the Shapley values of the associated finite games. This paper should then be considered as a generalization of the results of the work by Aumann-Shapley on nonatomic games.
Stochastic Dominance and Moments of Distributions
Authors: Fishburn Peter C.
Published: October 2008

Stochastic dominance orders of all finite degrees are defined on the set of distribution functions on the nonnegative real numbers in terms of integrals of the distributions. It is proved that if F strictly nth-degree stochastically dominates G, and if the moments of F and G through order n are finite with μFk = ∫Xk dF (x), then (μF1, …, μFn) ≠ (μG1, …, μGn) and (−1)k−1 μFk > (−1)k−1 μGk for the smallest k for which μFk ≠ μGk.
Characterization of Optimal Policies in Vector-Valued Markovian Decision Processes
Authors: Furukawa Nagata
Published: October 2008

Infinite horizon Markovian decision processes with Rp-valued additive utilities are considered. The optimization criterion, here, is a pseudo-order preference relation induced by a convex cone in Rp. The state space is a countable set, and the action space is a compact metric space. Certain assumptions on the continuity of the reward vector and the transition probability are made. In this setting, an algorithm improving policies with respect to the chosen preference relation is given. A point-to-set mapping is defined, and optimal policies are characterized by fixed points of the mapping which are maximal in the set of all fixed points.
Converting Linear Programs to Network Problems
Authors: Bixby Robert E. , Cunningham William H.
Published: October 2008

We describe an algorithm which converts a linear program min{cx ∣ Ax = b, x ≥ 0} to a network flow problem, using elementary row operations and nonzero variable-scaling, or shows that such a conversion is impossible. If A is in standard form, the computational effort required is bounded by O(rn), where r is the number of rows and n is the number of nonzero entries of A. A method for determining whether a “binary matroid” is “graphic” plays an important role in the algorithm.
The Discrete Sequential Search Problem with Nonrandom Cost and Overlook Probabilities
Authors: Wegener Ingo
Published: October 2008

Suppose one object is hidden in the kth of n boxes with probability p(k). The boxes are to be searched sequentially. Associated with the jth search of box k is a cost c(j, k) and a conditional probability q(j, k) that the first j − 1 searches of box k are unsuccessful while the jth search is successful given that the object is hidden in box k.

The problem is to minimize the expected cost of a strategy which at last surely finds the object. Without further assumptions we give necessary and sufficient conditions for the existence of admissible strategies with finite expected cost and the existence of optimal strategies. We give a procedure for the computation of an optimal strategy.
A General Failure Model: Optimal Replacement with State Dependent Replacement and Failure Costs
Authors: Nummelin E.
Published: October 2008

We shall consider the optimal replacement of a unit which is subject to random failure. It is assumed that there exists a hazard rate process rt, adapted to the history of the unit and, for a fixed t, denoting the conditional probability density of failure at t, given that the unit has not failed until t. If the unit is functioning at t, it can be replaced by a new one and a random replacement cost ct depending on the history of the unit up to t is incurred. If the unit fails at t, then it is replaced, and in addition to the replacement cost, a failure cost Kt, depending on the history of the unit, is incurred. The optimality criterion is the minimization of the total long run average cost per unit time. Our model generalizes the model of Bergman (Bergman, B. 1978. Optimal replacement under a general failure model. Adv. Appl. Probab. 10 431–444.) by allowing the state-dependence of the replacement and failure costs. The main result of the present paper states that there exists an optimal replacement rule, and that it is a threshold rule for the process γt = dct/dt + Ktrt. This means that there exists a* < ∞, such that an optimal replacement rule is to replace at the time when the process rt (assumed to be nondecreasing) reaches the level a*, or if failure occurs before this, to replace at failure. An iterative procedure is given for the determination of the threshold value a*.
The Relaxation Method for Solving Systems of Linear Inequalities
Authors: Goffin J. L.
Published: October 2008

The relaxation method for solving systems of inequalities is related both to subgradient optimization and to the relaxation methods used in numerical analysis.

The convergence theory depends upon two condition numbers. The first one is used mostly for the study of the rate of geometric convergence. The second is used to define a range of values of the relaxation parameter which guarantees finite convergence. In the case of obtuse polyhedra, finite convergence occurs for any value of the relaxation parameter between one and two.

Various relationships between the condition numbers and the concept of obtuseness are established.
Circular Cuts in a Network
Authors: Hu T. C. , Ruskey F.
Published: October 2008

A network consists of a set of nodes Vi (i = 1,…, n) with weights wi and a set of arcs connecting nodes Vi and Vj with arc capacity bij. The circular cut problem is to pick a subset of nodes containing V1 such that the total weight of the subset is less than a prescribed constant and the total arc capacity needed to separate the subset from the rest of the network is minimum.

As special cases this problem reduces to the MAX-FLOW-MIN-CUT problem and to a 0-1 knapsack problem. In this paper we present techniques for reducing the size of the problem. This is done by reducing the number of cuts that need to be considered and by condensing certain nodes.
Optimal Parameter Selection of Parabolic Systems
Authors: Reid D. W. , Teo K. L.
Published: October 2008

An optimal parameter selection problem is posed based upon a distributed parameter system with the parameters to be determined appearing in the coefficients of the partial differential equation. For this problem, an analytic expression is derived for the gradient of the performance criterion as a function of the parameters. For illustration, an example concerning advertising is solved.
Values and Derivatives
Authors: Mertens Jean-François
Published: October 2008

The diagonal formula in the theory of nonatomic games expresses the idea that the Shapley value of each infinitesimal player is his marginal contribution to the worth of a “perfect sample” of the population of all players, when averaged over all possible sample sizes. The concept of marginal contribution is most easily expressed in terms of derivatives; as a result, the diagonal formula has heretofore only been established for spaces of games that are in an appropriate sense differentiable (such as pNA or pNAD). In this paper we use an averaging process to reinterpret and then prove the diagonal formula for much larger spaces of games, including spaces (like bv'NA) in which the games cannot be considered differentiable and may even have jumps (e.g., voting games). The new diagonal formula is then used to establish the existence of values on even larger spaces of games, on which it had not previously been known that there exists any operator satisfying the axioms for the Shapley value.
Cooperative Fuzzy Games
Authors: Aubin Jean-Pierre
Published: October 2008

We derive versions of known results dealing with core, equilibria and Shapley-values of cooperative games in the case of cooperative fuzzy games, i.e., games defined on fuzzy subsets of the set of n players. A fuzzy coalition is an n-vector τ = (τi) associating with each player i his “rate of participation” τi ∈ [0, 1] in the fuzzy coalition and the real number v(·) is the coalition worth, assumed to be positively homogeneous. If also v is superadditive, or equivalently concave, the fuzzy game with side payments has a nonempty core. Associated with the coalition-worth function for any ordinary game with side payments is a fuzzy extension thereof, viz., the fuzzy game whose coalition-worth function is the least positively-homogeneous superadditive function majorizing the coalition-worth function of the original game. The fuzzy extension always has a nonempty core. Moreover, if the original game has a nonempty core, it coincides with that of its fuzzy extension. Analogous results are established for games without side payments. An axiomatization of “values” of fuzzy games with side payments is also given. The results are applied to show that the set of Walras equilibria coincides with the fuzzy core of an economy.
Discontinuous Optimization by Smoothing
Authors: Zang Israel
Published: October 2008

We present a simple tool for solving many discontinuous optimization problems. The basic idea is to express discontinuities by means of a step function, and then to approximate the step function by a smooth one. This way, a smooth once or twice continuously differentiable approximate problem is obtained. This problem can be solved by any gradient technique. The approximations introduced contain a single parameter, which controls their accuracy so that the original problem is replaced only in some neighborhoods of the points of discontinuity. Some convergence properties are established, and numerical experiments with some test problems are reported.
Minimization by Random Search Techniques
Authors: Solis Francisco J. , Wets Roger J.-B.
Published: October 2008

We give two general convergence proofs for random search algorithms. We review the literature and show how our results extend those available for specific variants of the conceptual algorithm studied here. We then exploit the convergence results to examine convergence rates and to actually design implementable methods. Finally we report on some computational experience.
Location on Tree Networks: P-Centre and n-Dispersion Problems
Authors: Chandrasekaran R. , Daughety A.
Published: October 2008

We consider two problems of locating facilities on trees. In the first, we wish to determine the location of n points so as to maximize the minimum distance between any pair. In the second we wish to locate p centers of a single type of facility so as to minimize the maximum distance between any point and the center nearest to it. We provide polynomial algorithms for both problems, of O(|N|2 log n · log |N|) for the first problem and of O(|N|2 log p) for the second, where |N| is the number of nodes in the tree.
Optimal Auction Design
Authors: Myerson Roger B.
Published: October 2008

This paper considers the problem faced by a seller who has a single object to sell to one of several possible buyers, when the seller has imperfect information about how much the buyers might be willing to pay for the object. The seller's problem is to design an auction game which has a Nash equilibrium giving him the highest possible expected utility. Optimal auctions are derived in this paper for a wide class of auction design problems.
Information Conditions, Communication and General Equilibrium
Authors: Dubey Pradeep , Shubik Martin
Published: October 2008

It is shown that if the information sets of one game are a refinement of the information sets of the other, then the set of pure strategy equilibrium points of the game with less information is contained within the set of pure strategy equilibrium points of the game with more information.
The Compensation Method Applied to a One-Product Production/Inventory Problem
Authors: Graves Stephen C. , Keilson Julian
Published: October 2008

This paper considers a one-product, one-machine production/inventory problem. Demand requests for the product are governed by a Poisson process with demand size being an exponential random variable. The production facility may be in production or idle; while in production, the facility produces continuously at a constant rate. The objective is to minimize system costs consisting of setup costs, inventory holding costs, and backorder costs. Given a two-critical-number policy, the problem is analyzed as a constrained Markov process using the compensation method. A closed-form expression is found for system cost as a function of the policy parameters. This cost function may then be searched to find an optimal policy.

The production/inventory problem is related to a server backlog process for an M/M/1 system in which the server departs when the system empties, and returns when the backlog exceeds a specified threshold. The application of the compensation method to this server backlog process is discussed.
A Stochastic Process Approach to Multivariate Reliability Systems: Notions Based on Conditional Stochastic Order
Authors: Arjas Elja
Published: October 2008

The purpose of this paper is to introduce extensions of the well known notions IRF, DFR, NBU, and NWU in reliability theory. These extensions are applicable when considering complex multicomponent systems, where the components are not necessarily behaving independently and where, by continuous observation of the system, its past at any time t is known to some degree. The definitions are in terms of conditional stochastic order of the system's or its components' residual lifetimes, given the σ-field corresponding to observed past.
On Team Guessing with Independent Information
Authors: Witsenhausen H. S.
Published: October 2008

Team theory is the study of situations in which a set of cooperating agents, called a team, each with access to different data or information, attempt to optimize a common criterion, under rules which restrict communication between agents. Team theory is of interest in theoretical studies in economics, communication and control.

A very simple example of a team situation is the following. Each of the team's n agents attempts to ascertain whether or not a certain random event E of probability ½ has occurred. Agent i must base his decision solely on the observation of random variable Ui and the team's goal is to minimize p̄ = n−1 ∑pi, where pi is the probability that agent i makes an error. The main result of this paper is to show that when the variables U1, …, Un are independent, this alone places a positive lower bound on p̄, no matter what the joint distribution of E and the data {Ui} may be.

For each n the exact lower bound is determined: it is [Formula: see text] for n = 2, ¼ for n = 3 and as n goes to infinity it is asymptotic to [Formula: see text]
Algorithms for Linear Programming Problems with Interval Objective Function Coefficients
Authors: Steuer Ralph E.
Published: October 2008

This paper presents three algorithms for solving linear programming problems in which some or all of the objective function coefficients are specified in terms of intervals. Which algorithm is applicable depends upon (a) the number of interval objective function coefficients, (b) the number of nonzero objective function coefficients, and (c) whether or not the feasible region is bounded. The algorithms output all extreme points and unbounded edge directions that are “multiparametrically optimal” with respect to the ranges placed on the objective function coefficients. The algorithms are most suitable to linear programs in which the objective function coefficients are deterministic but are likely to vary from time period to time period (as for example in blending problems).
Globally Convergent Algorithms for Convex Programming
Authors: Rosenberg Eric
Published: October 2008

We consider solving a (minimization) convex program by sequentially solving a (minimization) convex approximating subproblem and then executing a line search on an exact penalty function. Each subproblem is constructed from the current estimate of a solution of the given problem, possibly together with other information. Under mild conditions, solving the current subproblem generates a descent direction for the exact penalty function. Minimizing the exact penalty function along the current descent direction provides a new estimate of a solution, and a new subproblem is formed. For any arbitrary starting estimate, this scheme generates a sequence of estimates that converges to a solution of the given problem. Moreover, the functions defining the given problem and each subproblem need not be differentiable.
Equivalence of LCP and PLS
Authors: Eaves B. C. , Lemke C. E.
Published: October 2008

It is our purpose here to show that two prototype models of complementary pivot and fixed point theory and the corresponding path following solution methods are conceptually equivalent.
Regularity and Stability of Equilibrium Points of Bimatrix Games
Authors: Jansen M. J. M.
Published: October 2008

This paper deals with regular equilibrium points. Using properties of such equilibrium points, it is possible to give short proofs of known facts about completely mixed bimatrix games and bimatrix games with a unique equilibrium point. We prove that a bimatrix game with a convex equilibrium point set or with a finite number of equilibrium points has a regular equilibrium point. We shall show, moreover, that the class of all m × n-bimatrix games (m, n ∈ ℕ) for which all the equilibrium points are regular, is an open and dense subset of the class of all m × n-bimatrix games. Furthermore, it is shown that an isolated equilibrium point of a bimatrix game is stable if and only if it is a regular one. Here, we call an equilibrium point of a bimatrix game stable if, roughly speaking, all bimatrix games in a neighborhood of the game in question have an equilibrium point close to it.
The Failure and Hazard Processes in Multivariate Reliability Systems
Authors: Arjas Elja
Published: October 2008

The component failures in a complex multi-component system are treated in the paper as a multivariate point process, and the system failure as a univariate point process derived from this. Our main concern is to extend the well-known concept of a hazard function to this general case. It is suggested that, e.g., the system failure hazard be defined as a stochastic process, viz., the compensator of the system failure counting process relative to the σ-fields describing the system's past. The connections between such a hazard process and the lifetime distribution classes of Arjas (Arjas, E. 1981. A stochastic process approach to multivariate reliability systems: Notions based on conditional stochastic order. Math. Oper. Res. 6 263–276.) are also discussed.
The Number of Outcomes in the Pareto-Optimal Set of Discrete Bargaining Games
Authors: O'Neill Barry
Published: October 2008

A set of n players is to bargain over which one of m possible outcomes will be chosen. The preference of outcome i to player j is assumed to be a random variable with all preference rankings equally likely and without ties. This would arise in case the payoffs are chosen as independent samplings from a continuous distribution Fj. The mean and distribution of the number of outcomes in the Pareto-optimal set are calculated for finite m. As m → ∞ the mean is asymptotic to (log m + 0.577)n−1/(n − 1)! and for n = 2, m → ∞, the distribution approaches the normal distribution. The results are also applied to a problem in multiattribute utility theory. Suppose we wish to select an individual with high values on two personal attributes that are independent and continuously measurable. Of a world population of four billion, the efficient set would have an expectation of 22.7 individuals.
Insensitive Generalized Semi-Markov Schemes with Point Process Input
Authors: Helm Werner E. , Schassberger Rolf
Published: October 2008

Where sequences of i.i.d. random variables are used for modelling successive repair limes, life times, service times, etc, it can happen that stationary probabilities are found for the—suitably defined—system state, which depend only on the means of those variables, not on any further characteristics of their distributions. The well-known Erlang loss model provides an example. For a large class of models, Jansen, Koenig, and Nawrotzki (Jansen, U., D. Koenig, K. Nawrotzki. 1979. A criterion of insensitivity for a class of queuing systems with random marked point processes. Math. Operationsforsch. Statist. 10 379–403.) have shown that, whenever such insensitivity prevails towards an i.i.d. sequence or—equivalently—a renewal process, then replacing this process by an arbitrary point process with the same intensity (when stationary) still does not change the stationary distribution of the system state. We extend their model and prove the analogous result by way of a different technique of general interest.
Odd Minimum Cut-Sets and b-Matchings
Authors: Padberg Manfred W. , Rao M. R.
Published: October 2008

We show that the determination of a minimum cut-set of odd cardinality in a graph with even and odd vertices can be dealt with by a minor modification of the polynomially bounded algorithm of Gomory and Hu for multi-terminal networks. We connect this problem to the problem of identifying a matching (or blossom) constraint that chops off a point which is not contained in the convex hull of matchings or proving that no such inequality exists. Both the b-matching problems without and with upper bounds are considered. We discuss how the results of this paper can be used in conjunction with commercial LP packages lo solve b-matching problems.
Leontief Substitution Systems and Matroid Complexes
Authors: Provan J. Scott , Billera Louis J.
Published: October 2008

A (pre-) Leontief substitution system is a linear system Ax = b, x > 0, where b is a nonnegative vector and A is a matrix containing at most one positive element in each column. We investigate the face structure of nondegenerate Leontief substitution systems by looking at the corresponding dual simplicial complex. A characterization of the face structure is given for the bounded case (called a totally pre-Leontief substitution system by Dantzig and Veinott), and it is shown that the dual complex always comprises the independent sets of a matroid. Conversely, a characterization is given for the class of matroids whose independent sets form the dual complex to a polyhedron, and it is shown that this polyhedron can always be chosen to be a (not necessarily bounded) Leontief substitution system. The number of such matroids is also given as functions of the rank and the cardinality of the base set. and the number of nondegenerate totally (pre-) Leontief substitution systems is given as functions of the number of equalities and the number of variables.
A Refinement Procedure for Computing Fixed Points Using Scarf's Primitive Sets
Authors: van der Heyden Ludo
Published: October 2008

A fixed point of a function is a point that coincides with its image when applying the function. Fixed point computations originated with Scarf (Scarf, H. 1967. The approximation of fixed points of a continuous mapping. SIAM J. Appl. Math. 15 1328–1343.) who presented a finite combinatorial method for finding an approximate fixed point. The method is a systematic search through a sequence of combinatorial objects called primitive sets and provides a constructive proof for a theorem whose domain of applicability goes beyond fixed point computations.

In this paper we present a refinement method for proving Scarf's theorem. A refinement method solves the main problem, as formulated in Scarf's theorem, by solving a succession of subproblems. A solution for a subproblem is an approximate solution for the main problem. It is also the starting point for solving a more refined subproblem whose solution we expect to have greater accuracy than the approximate solution we started with. Subproblems are solved continuously until a solution of sufficient accuracy has been found.

An interesting feature of the refinement method is its possibly nonmonotonic behavior. The method sometimes regresses to a subproblem solved earlier. Several regressions may follow each other, but eventually the method returns to a forward mode. Index theoretic arguments enable us to characterize the points where the procedure behaves nonmonotonically.

Finally, we relate our approach to that of Tuy (Tuy, H. 1979. Pivotal methods for computing equilibria: Unified approach and new restart algorithm. Math. Programming 16 210–227.) and establish that both methods coincide. We also show how Scarfs original method can be considered a special case of the refinement method presented here.
An Efficient Optimal Algorithm for the Two-Machines Unit-Time Jobshop Schedule-Length Problem
Authors: Hefetz N. , Adiri I.
Published: October 2008

The problem of scheduling a two-machine unit-operation-time jobshop to complete all jobs as rapidly as possible is shown to be solved by the following rule. Select for service from available jobs at each stage one with longest remaining processing time. The running time and storage space of the rule are both linear functions of the total number of operations, thereby establishing that the problem belongs to P.
Private Information and Pure-Strategy Equilibria
Authors: Radner Roy , Rosenthal Robert W.
Published: October 2008

In this paper it is proved that in games with a finite number of players and a finite number of moves, if each player observes a private information random variable which has an atomless distribution and is independent of the observations and payoffs of all other players, then the game possesses a pure-strategy equilibrium. Examples are presented that illustrate the importance of the assumptions.
Maximising Real-Valued Submodular Functions: Primal and Dual Heuristics for Location Problems
Authors: Wolsey Laurence A.
Published: October 2008

Recently it has been shown how various results on the behaviour of exact and approximate primal algorithms for certain discrete location problems can be obtained by studying the more general problem of maximising a submodular set function. Unfortunately, this more general model tells us little about an important aspect of the discrete location problems, their linear programming relaxations and the possible use of dual solutions in obtaining bounds.

Here we examine a slightly more specialised model that again generalises the location problems of interest, but now also includes the continuous aspects of the problems missing from the earlier model, namely the problem: max{w(y): ∑j=1najyj ≤ b, 0 ≤ yj < 1} of maximising a real-valued nondecreasing piecewise linear, concave submodular function subject to a knapsack constraint. We show that a continuous greedy heuristic always attains at least (1 − e−1) × 100% of the optimal value, and that for the discrete problem an adapted greedy heuristic always attains 35% of the optimal value.

Specialised to the capacitated and uncapacitated location problems these results permit us to strengthen earlier results, and to obtain new results on dual greedy heuristics.
Some Distribution-Independent Results About the Asymptotic Order of the Average Number of Pivot Steps of the Simplex Method
Authors: Borgwardt Karl-Heinz
Published: October 2008

This paper is concerned with the average number of pivot steps of the Simplex Method which are required to solve linear programming problems of the following kind: [Formula: see text] We investigate a certain variant of the Simplex Method, which is particularly suited for theoretical considerations. For every pair (m, n) (m ≥ n) we introduce probability spaces whose random samples are the linear programming problems of the above mentioned type. The vectors ai, v are supposed to be distributed independently, identically and symmetrically under rotations on a bounded subset of ℝn. We deduce upper and lower bounds for the expectation values of the number of steps required in phase II of the Simplex Method. The evaluation of these bounds yields the following result for m → ∞ and for fixed n:

(1) The expectation values become O(m1/(n−1)).

(2) There exists a distribution whose expectation values increase like m1/(n−1).

(3) For any distribution which satisfies our conditions the expectation values tend to infinity.

(4) For every ϵ > 0 there are distributions whose expectation values become O(mϵ).
Morse Programs: A Topological Approach to Smooth Constrained Optimization
Authors: Fujiwara Okitsugu
Published: October 2008

The purpose of this paper is to give a geometrical answer to the question to the strong second order sufficiency conditions hold at any local minimum point for almost all nonlinear programs? Our idea is to reduce the nonlinear programming problem to a finite family of “well-behaved” nonlinear programs by perturbing the objective function in a linear fashion and perturbing the right-hand side of the constraints by adding a constant. Each of the “well-behaved” nonlinear programs will consist of minimizing a Morse function on a manifold with boundary, where the Morse function has no critical points on the boundary.
The Economics of Matching: Stability and Incentives
Authors: Roth Alvin E.
Published: October 2008

This paper considers some game-theoretic aspects of matching problems and procedures, of the sort which involve matching the members of one group of agents with one or more members of a second, disjoint group of agents, ail of whom have preferences over the possible resulting matches. The main focus of this paper is on determining the extent to which matching procedures can be designed which give agents the incentive to honestly reveal their preferences, and which produce stable matches.

Two principal results are demonstrated. The first is that no matching procedure exists which always yields a stable outcome and gives players the incentive to reveal their true preferences, even though procedures exist which accomplish either of these goals separately. The second result is that matching procedures do exist, however, which always yield a stable outcome and which always give all the agents in one of the two disjoint sets of agents the incentive to reveal their true preferences.
Analysis of a Dynamic Duopoly Model of Advertising
Authors: Jones Philip C.
Published: October 2008

This paper presents a dynamic model of advertising in a duopoly and studies sales response to steady-state advertising policies. With steady-state advertising policies, sales levels must converge to one of a finite number of equilibria, and the equilibrium set consists of sinks and saddles with one more sink than saddle. When advertising is allowed to vary, the model may admit hysteresis; and we present an example which shows that accounting for word-of-mouth advertising can lead to hysteresis.
A Light-Traffic Theorem for Multi-Server Queues
Authors: Burman David Y. , Smith Donald R.
Published: October 2008

Several approximations for the expected delay in an M/G/c queue depend on both its light- and heavy-traffic behavior. Although the required heavy-traffic result has been proved, the light-traffic result has only been conjectured by Boxma, Cohen, and Huffels. We prove this conjecture when the service is of phase-type; intuitively, any M/G/c queue can be arbitrarily closely approximated by such a system. In particular, as the traffic goes to zero, we show that the probability of delay depends only on the mean of the service-time distributions and that the delay (when positive) converges in distribution to the minimum of c independent equilibrium-excess service-times. This result justifies an efficient computational approach to obtain numerical results for M/G/c queues and provides useful methodology for the approximation of other complicated stochastic systems.
On the Existence of Pareto Efficient Points
Authors: Borwein Jonathan M.
Published: October 2008

We prove some general theorems on the existence of minimal points of compact sets in linear spaces with respect to closed convex orderings. These results are compared to the axiom of choice.
A Fast Algorithm for the Decomposition of Graphs and Posets
Authors: Buer Hermann , Möhring Rolf H.
Published: October 2008

Many combinatorial (optimization) problems of graphs (e.g., finding maximal independent sets or maximum matchings) and acyclic networks (e.g., finding shortest paths or maximum flows) can be solved by means of decomposition of the graph (network) into autonomous subsets. (Given a relation R on A, a subset B of A is called autonomous, if for each α ∈ A\B the following holds: if (α, β0) ∈ R for some β0 ∈ B, then (α, β) ∈ R for all β ∈ B; if (β0, α) ∈ R for some β0 ∈ B, then (β, α) ∈ R for all β ∈ B). We present an algorithm which finds all autonomous subsets of graphs and posets with p points in O(p3) time and O(p2) space. The ideas behind this algorithm reveal rather strong connections between graph decomposition, homomorphisms of graphs and posets, and comparability graph recognition. Furthermore, the well-known series-parallel decomposition for graphs and posets is contained as a special case.
Jointly Constrained Biconvex Programming
Authors: Al-Khayyal Faiz A. , Falk James E.
Published: October 2008

This paper presents a branch-and-bound algorithm for minimizing the sum of a convex function in x, a convex function in y and a bilinear term in x and y over a closed set. Such an objective function is called biconvex with biconcave functions similarly defined. The feasible region of this model permits joint constraints in x and y to be expressed. The bilinear programming problem becomes a special case of the problem addressed in this paper. We prove that the minimum of a biconcave function over a nonempty compact set occurs at a boundary point of the set and not necessarily an extreme point. The algorithm is proven to converge to a global solution of the nonconvex program. We discuss extensions of the general model and computational experience in solving jointly constrained bilinear programs, for which the algorithm has been implemented.
Approximate Purification of Mixed Strategies
Authors: Aumann R. J. , Katznelson Y. , Radner R. , Rosenthal R. W. , Weiss B.
Published: October 2008

Under relatively weak conditions on the information structure of a game it is shown that any mixed strategy of a player can be replaced by a certain pure strategy without affecting any player’s expected payoff appreciably, no matter what strategies the other players use. Under even weaker conditions the existence of a Nash equilibrium in mixed strategies is shown to guarantee the existence of a pure-strategy combination which is an approximate equilibrium.
Affine Structure and Invariant Policies for Dynamic Programs
Authors: Denardo Eric V. , Rothblum Uriel G.
Published: October 2008

This paper studies a family of sequential decision processes whose affine structure is shown to imply that attention can be restricted to policies that select the same decision for all states. A sequence of n invariant policies (decisions) is shown to be optimal when the planning horizon is n epochs. When the planning horizon is infinite, added structure is imposed, and a stationary invariant policy is shown to be optimal. Computational methods and examples are included.
Stationary Policies in Dynamic Programming Models Under Compactness Assumptions
Authors: Schäl Manfred
Published: October 2008

The present work deals with the usual stationary decision model of dynamic programming. The imposed convergence condition on the expected total rewards is so general that both the negative (unbounded) case and the positive (unbounded) case are included. However, the gambling model studied by Dubins and Savage is not covered by the present model.

In addition to the convergence condition, a continuity and compactness condition is imposed. The main result states that the supremum of the expected total rewards under all stationary policies is equal to the supremum under all (possibly randomized and non-Markovian) policies.
Optimal Control of the Diffusion Coefficient of a Simple Diffusion Process
Authors: McNamara J. M.
Published: October 2008

We consider the optimal control of a one-dimensional diffusion process over a finite time interval. The process may be controlled by varying the diffusion coefficient. The objective is to maximize the expected value of some function of the state, R, at final time. In this paper we investigate the properties of a particular bang-bang control σ0, and find necessary and sufficient conditions on R for σ0 to be optimal.
Adjoint Process Duality
Authors: Borwein J. M.
Published: October 2008

We study convex processes between topological vector spaces with particular emphasis on their adjoints. This study is then applied to produce general duality results for classes of convex programs involving processes. The use of processes allows one to exploit the symmetry of linear programming and to obtain significantly broader and stronger results.
Proper Efficiency in Nonconvex Multicriteria Programming
Authors: Choo E. U. , Atkins D. R.
Published: October 2008

Proper efficient solutions of nonconvex vector maximum problems can be generated by solving a parametric family of ordinary nonlinear programs. This parametric scheme follows from the characterization of proper efficiency by an extended form of the generalized Tchebycheff norm.
A Duality Theory for Infinite-Horizon Optimization of Concave Input/Ouput Processes
Authors: Evers Joseph J. M.
Published: October 2008

A general concave ∞-horizon optimization model is analyzed with the help of a special convexity concept, which combines both the usual convexity and the dynamic structure. The axiomatic setup leads to a perfect symmetry between the primal and dual problems. After introducing a particular dynamic feasibility hypothesis, the following results are presented: (i) boundedness of trajectories as a necessary condition for optimally, (ii) the existence of primal and dual optimal trajectories, (iii) approximation by finite horizon models, and (iv) necessary and sufficient conditions for optimality.
Analysis of Heuristics for Stochastic Programming: Results for Hierarchical Scheduling Problems
Authors: Dempster M. A. H. , Fisher M. L. , Jansen L. , Lageweg B. J. , Lenstra J. K. , Rinnooy Kan A. H. G.
Published: October 2008

Certain multistage decision problems that arise frequently in operations management planning and control allow a natural formulation as multistage stochastic programs. In job shop scheduling, for example, the first stage could correspond to the acquisition of resources subject to probabilistic information about the jobs to be processed, and the second stage to the actual allocation of the resources to the jobs given deterministic information about their processing requirements. For two simple versions of this two-stage hierarchical scheduling problem, we describe heuristic solution methods and show that their performance is asymptotically optimal both in expectation and in probability.
On the Uncapacitated Plant Location Problem. I: Valid Inequalities and Facets
Authors: Cho D. Chinhyung , Johnson Ellis L. , Padberg Manfred , Rao M. R.
Published: October 2008

The uncapacitated plant location problem is considered as a node-packing problem. For this problem, several valid inequalities and facets are discussed. Necessary and sufficient conditions for trivial facets along with necessary conditions for nontrivial facets are derived. In addition, all of the facets for the case of three plants and three or more destinations are identified.
An Application of the Aumann-Shapley Prices for Cost Allocation in Transportation Problems
Authors: Samet Dov , Tauman Yair , Zang Israel
Published: October 2008

The Aumann-Shapley (A-S) prices are axiomatically determined on certain classes of piecewise continuously differentiable cost functions. One of these classes consists of all cost functions derived from the transportation problems and some of their generalizations. These prices are used here to allocate costs among destinations in a way that each destination will pay its “real part” in the total transportation costs. An economic transportation model is presented in which the A-S prices are compatible with consumer demands. Finally an algorithm is provided to calculate both the optimal solution and the associated A-S prices for transportation problems.
On Random Binary Trees
Authors: Brown Gerald G. , Shubert Bruno O.
Published: October 2008

A widely used class of binary trees is studied in order to provide information useful in evaluating algorithms based on this storage structure. A closed form counting formula for the number of binary trees with n nodes and height k is developed and restated as a recursion more useful computationally. A generating function for the number of nodes given height is developed and used to find the asymptotic distribution of binary trees. An asymptotic probability distribution for height given the number of nodes is derived based on equally likely binary trees. This is compared with a similar result for general trees.

Random binary trees (those resulting from a binary tree sorting algorithm applied to random strings of symbols) are counted in terms of the mapping of permutations of n symbols to binary trees of height k. An explicit formula for this number is given with an equivalent recursive definition for computational use. A generating function is derived for the number of symbols given height. Lower and upper bounds on random binary tree height are developed and shown to approach one another asymptotically as a function of n, providing a limiting expression for the expected height.

The random binary trees are examined further to provide expressions for the expectations of the number of vacancies at each level, the distribution of vacancies over all levels, the comparisons required for insertion of a new random symbol, the fraction of nodes occupied at a particular level, the number of leaves, the number of single vacancies at each level, and the number of twin vacancies at each level. A random process is defined for the number of symbols required to grow a tree exceeding any given height.

Finally, an appendix is given with sample tabulations and figures of the distributions.