bluuebunny/crossref_metadata_2025 huggingface dataset:
Assessing Purchase Timing Models: Whether or Not is Preferable to When
Authors: Wheat Rita D. , Morrison Donald G.
Published: October 2008

Two types of purchase timing models—those which model purchase incidence (whether or not) and those which model interpurchase time (when)—are examined. We show that modelling purchase incidence is almost always preferable to modelling interpurchase time. We also derive upper bound R2's for purchase incidence models. These R2's serve as useful benchmarks for assessing the goodness-of-fit of empirical choice models.
Multiproduct Advertising Budgeting
Authors: Doyle Peter , Saunders John
Published: October 2008

The problem of optimizing advertising across a broad product range, where significant cross elasticities are likely, is explored. A linear-in-logs model is proposed and allocation rules for budgeting across products and media are derived. The model is estimated for a large European variety store chain. The results suggest profits could be increased by nearly 40 percent with no change in the advertising budget, if management shifted from the conventional bottom-up approach to the more systematic method outlined. The final section describes how management implemented the model.
Price Promotions: Limiting Competitive Encroachment
Authors: Lal Rajiv
Published: October 2008

In this paper, we explore equilibrium pricing strategies in an infinite horizon repeated game for an oligopoly. We model the interactions between three firms in a market of switchers and loyals. Our analysis shows that if, there are sufficiently large number of switchers in the market, the demand parameter is within an acceptable range, and the firms have a sufficiently low discount rate, alternating promotions between national firms can be an outcome of a perfect Nash equilibrium between competing firms. This equilibrium results in an implicit collusion between national firms and therefore suggests that price promotions can be interpreted as a long run strategy pursued by national firms to defend their market shares from possible encroachments of a third firm. In this way we attempt to provide an explanation for the patterns of promotion observed in some industries and in particular the beverage industry.
Compensating Heterogeneous Salesforces: Some Explicit Solutions
Authors: Rao Ram C.
Published: October 2008

This paper considers the question of how a sales manager should design the optimal compensation scheme for his salesforce when it consists of salespersons of varying selling skills, i.e., when the salesforce is heterogeneous. The manager's problem is to reward the salespersons based on observable, uncertain sales achieved by the salespersons. Under the assumption that both the manager and the salespersons are risk neutral, the optimal compensation scheme is derived. It consists of the manager offering a menu of plans, consisting of a quota, a payment for meeting quota, and a constant commission rate for sales above or below quota. Such schemes using constant commission rates are also called menus of linear plans. Salespersons choose the quota which best suits them, achieve sales, and are then rewarded based on their actual performance. This scheme, variants of which are often observed in practice, is shown to be optimal for sales environments characterized by commonly encountered sales response functions, and a large class of frequency distributions of selling skills in the salesforce. The problem is solved using the methods of principal-agent models. The key differences in managing homogeneous and heterogeneous salesforces are highlighted. Finally, the paper discusses the issues involved in practically implementing the optimal compensation scheme.
Orientation in Complementary Pivot Algorithms
Authors: Todd Michael J.
Published: October 2008

Shapley introduced an index theory for bimatrix games that oriented the paths generated by the Lemke-Howson algorithm and thus partitioned equilibrium points into two sets. Here we develop a similar orientation theory for a generalized complementary pivot algorithm and apply our results to bimatrix games, the linear complementarity problem, and fixed point algorithms. We provide the weakest known general sufficiency conditions (based on those of Garcia) for Lemke's algorithm to process the linear complementarity problem. We also show that if the linear complementarity version of a quadratic programming problem is solved and gives a Kuhn-Tucker solution, then the hessian of the objective function restricted to the subspace of active constraints has positive determinant. Finally we show that fixed point algorithms will only approximate fixed points of f at which the determinant of the Jacobian of f minus the identity has the appropriate sign.
The Complexity of Flowshop and Jobshop Scheduling
Authors: Garey M. R. , Johnson D. S. , Sethi Ravi
Published: October 2008

NP-complete problems form an extensive equivalence class of combinatorial problems for which no nonenumerative algorithms are known. Our first result shows that determining a shortest-length schedule in an m-machine flowshop is NP-complete for m ≥ 3. (For m = 2, there is an efficient algorithm for finding such schedules.) The second result shows that determining a minimum mean-flow-time schedule in an m-machine flowshop is NP-complete for every m ≥ 2. Finally we show that the shortest-length schedule problem for an m-machine jobshop is NP-complete for every m ≥ 2. Our results are strong in that they hold whether the problem size is measured by number of tasks, number of bits required to express the task lengths, or by the sum of the task lengths.
A New Approach to Lagrange Multipliers
Authors: Clarke Frank H.
Published: October 2008

We consider a mathematical programming problem on a Banach space, and we derive necessary conditions for optimality in Lagrange multiplier form. We prove further that “most mathematical programming problems are normal.” The novelty of our approach lies on the one hand in the absence of both differentiability and convexity hypotheses on the functions delimiting the problem, and on the other hand in the method of proof, which is new. The approach unifies the well-known smooth and convex cases besides treating a new general class of problems.

The main analytical tool in this paper is an extension to infinite-dimensional spaces of the “generalized gradient” previously introduced by the author. The calculus of the generalized gradient is explored as a preliminary step.
The Asymptotic Theory of Stochastic Games
Authors: Bewley Truman , Kohlberg Elon
Published: October 2008

We study two person, zero sum stochastic games. We prove that limn→∞{Vn/n} = limr→0rV(r), where Vn is the value of the n-stage game and V(r) is the value of the infinite-stage game with payoffs discounted at interest rate r > 0. We also show that V(r) may be expanded as a Laurent series in a fractional power of r. This expansion is valid for small positive r. A similar expansion exists for optimal strategies. Our main proof is an application of Tarski's principle for real closed fields.
A Successive Underestimation Method for Concave Minimization Problems
Authors: Falk James E. , Hoffman Karla R.
Published: October 2008

A new method designed to globally minimize concave functions over linear polyhedra is described. Properties of the method are discussed, an example problem is solved, and computational considerations are discussed.
Measurable Selection and Dynamic Programming
Authors: Evstigneev I. V.
Published: October 2008

A general multistage problem of stochastic optimization is studied. It is proved under some simple assumptions that the extremum in the problem is attained. The “Bellman functions” are constructed and a criterion of optimality in terms of these functions is given. The main tools used are measurable selection theorems. The paper generalizes the previous work of R. T. Rockafellar and R. J.-B. Wets devoted to the convex case.
Cooperation in Mixed Equilibrium
Authors: Moulin Hervé
Published: October 2008

Self-penalties of the players in a two-person game are studied as a cooperative tool: by committing himself to a penalty in case he plays a particular strategy, a player may improve upon the equilibrium payoff of both players. A complete characterization of this phenomenon is given for mixed equilibria.
The Asymptotic Solution of a Recursion Equation Occurring in Stochastic Games
Authors: Bewley Truman , Kohlberg Elon
Published: October 2008

We show that there exists a Laurent series in a fractional power of n which approximates Vn up to log n, where Vn is the value of an n-stage two person zero sum stochastic game. We prove this result by showing that the Laurent series is an approximate solution of the dynamical programming equation for Vn, Vn+1 = f(Vn). It seems that our methods could be used to find approximate solutions to other difference equations. Our proof makes repeated use of Tarski's principle for real closed fields.
An Ordinal Bargaining Set for Games Without Side Payments
Authors: Asscher Nechemia
Published: October 2008

Billera (Billera, L. J. 1968. On cores and bargaining sets for N-person cooperative games without side payments. Ph.D. dissertation, The City University of New York, 1968; Billera, L. J. 1970. Existence of general bargaining sets for cooperative games without side payments. Bull. Amer. Math. Soc. 76 375–379.] proposed a simple bargaining set for games without side payments, and announced it as an open question, whether his proposed bargaining set is never empty. An affirmative answer is given to Billera's question in this paper.
The Space of Polynomials in Measures is Internal
Authors: Reichert Joshua , Tauman Yair
Published: October 2008

We show that the algebra generated by nonatomic measures is an internal space. We then provide a natural alternative proof for the existence of a unique value on pNA.
Asymptotic Properties of the Quadratic Assignment Problem
Authors: Frenk J. B. G. , van Houweninge M. , Rinnooy Kan A. H. G.
Published: October 2008

For the general quadratic assignment problem as well as for a planar version of this problem, we extend earlier work by Burkard and Fincke to prove that the ratio of the maximal to the minimal solution value converges to 1 almost surely. In fact, any solution value can almost surely be written asymptotically as a simple, explicitly given function of the problem size. Theoretical analysis and computational experiments reveal the convergence to be relatively fast.
A 2-Person Game with Lack of Information on 1½ Sides
Authors: Sorin Sylvain , Zamir Shmuel
Published: October 2008

We consider a repeated 2-person 0-sum game with incomplete information about the pay-off matrix. Player I (maximizer) knows the real pay-off matrix but he is uncertain about the beliefs of his opponent. We show that in this case the Aumann-Maschler results on incomplete information on one side no longer hold. In particular such a game will not have a value in general, in spite of the fact that one player is fully informed about the state of nature.
The Strong Positivity Conditions
Authors: Reinoza Alfonso
Published: October 2008

In this paper we consider a class of generalized equations, which are a unified way of formulating problems of linear and nonlinear programming, complementarity, variational inequalities and mathematical economics among others. We introduce a set of conditions, which we call the strong positivity conditions, prove that they are sufficient for a solution of a generalized equation to be locally unique, and discuss their stability when the functions involved in the problem are subjected to small perturbations. Applications to linear generalized equations and nonlinear programming problems are discussed.
A Two-Resource Allocation Problem Solvable in Linear Time
Authors: Megiddo Nimrod , Ichimori Tetsuo
Published: October 2008

The allocation problem discussed here is as follows. The processing time of a task is a linear function t-ax-by of amounts x, y of resources allocated to it, where t, a, b are positive constants. Given the amounts X and Y of available resources, we wish to allocate them among n independent tasks so as to minimize the maximal completion time. We solve this problem in linear time.
A Best Possible Heuristic for the k-Center Problem
Authors: Hochbaum Dorit S. , Shmoys David B.
Published: October 2008

In this paper we present a 2-approximation algorithm for the k-center problem with triangle inequality. This result is “best possible” since for any δ < 2 the existence of δ-approximation algorithm would imply that P = NP. It should be noted that no δ-approximation algorithm, for any constant δ, has been reported to date. Linear programming duality theory provides interesting insight to the problem and enables us to derive, in O(|E| log |E|) time, a solution with value no more than twice the k-center optimal value.

A by-product of the analysis is an O(|E|) algorithm that identifies a dominating set in G2, the square of a graph G, the size of which is no larger than the size of the minimum dominating set in the graph G. The key combinatorial object used is called a strong stable set, and we prove the NP-completeness of the corresponding decision problem.
Complementary Pivoting Algorithms Involving Extreme Rays
Authors: Werner Roland , Wetzel Reinhard
Published: October 2008

We describe an extension of Lemke's complementary pivoting scheme involving extreme rays. Bases of extreme rays are introduced as a generalization of basic solutions. This avoids artificial effort concerning “constraints at infinity” or similar techniques. As an example the application to quadratic programming problems is discussed.
Second-Order Derivatives of Extremal-Value Functions and Optimality Conditions for Semi-Infinite Programs
Authors: Shapiro Alexander
Published: October 2008

Second-order differential properties of an extremal-value function v are studied. It is shown that under certain assumptions (in particular the strong second-order sufficiency conditions) v is locally expressible as the maximum of a finite number of C2-functions. After removing the assumption of strong sufficiency lower and upper bounds on the second order local behaviour of v are proposed. The obtained results are applied to give second-order optimally conditions for a semi-infinite program.
Equivalent N-Person Games and the Null Space of the Shapley Value
Authors: Kleinberg Norman L. , Weiss Jeffrey H.
Published: October 2008

Two n-person games may be said to be equivalent if they have the same Shapley value. In this paper, we attempt to simplify the determination of the equivalence of two games. We do this by recognizing that a pair of games are equivalent if and only if their difference lies in the null space of the Shapley value. Using the representation theory of the symmetric groups we construct a direct-sum decomposition of this null space into invariant subspaces. We then use this same theory to derive a characterization of a very general type of value, of which the Shapley value is one particular example.
A Primal-Dual Algorithm for Submodular Flows
Authors: Cunningham William H. , Frank András
Published: October 2008

Previously the only polynomial-time solution algorithm to solve the optimal submodular flow problem introduced by Edmonds and Giles was based on the ellipsoid method. Here, modulo an efficient oracle for minimizing certain submodular functions, a polynomial time procedure is presented which uses only combinatorial steps (like building auxiliary digraphs, finding augmenting paths). The minimizing oracle is currently available only via the ellipsoid method, in general; however in important special cases, such as network flows, matroid intersections, orientations, and directed cut coverings, the necessary oracle can be provided combinatorially.
The Entropic Penalty Approach to Stochastic Programming
Authors: Ben-Tal Aharon
Published: October 2008

A penalty-type decision-theoretic approach to Nonlinear Programming Problems with stochastic constraints is introduced. The Stochastic Program (SP) is replaced by a Deterministic Program (DP) by adding a term to the objective function to penalize solutions which are not “feasible in the mean.” The special feature of our approach is the choice of the penalty function PE, which is given in terms of the relative entropy functional, and is accordingly called entropic penalty. It is shown that PE has properties which make it suitable to treat stochastic programs. Some of these properties are derived via a dual representation of the entropic penalty which also enable one to compute PE more easily, in particular if the constraints in (SP) are stochastically independent. The dual representation is also used to express the Deterministic Problem (DP) as a saddle function problem. For problems in which the randomness occurs in the rhs of the constraints, it is shown that the dual problem of (DP) is equivalent to Expected Utility Maximization of the classical Lagrangian dual function of (SP), with the utility being of the constant-risk-aversion type. Finally, mean-variance approximations of PE and the induced Approximating Deterministic Program are considered.
Asymptotic Analysis of the Time Dependent M/M/1 Queue
Authors: Massey William A.
Published: October 2008

Using operator analytic techniques, we develop a nonstationary Markovian queueing theory starting with the M(t)/M(t)/1 queue. We employ an asymptotic approach quite different from the usual large time analysis. Instead, we uniformly accelerate the queue length process. That is, we divide the arrival and service rate by a common parameter ϵ. Then, for a fixed time interval, we consider the asymptotics for the distribution, mean, and variance of the queue length process as ϵ goes to zero. The effects of ϵ can be quite different for the given time interval. This gives us a dynamic asymptotic behavior for the queue length process. We can formulate a time dependent traffic intensity parameter that determines when the process is asymptotically stable and when it is asymptotically unstable.
Probabilistic Analysis of a Machine Scheduling Problem
Authors: Gazmuri Pedro G.
Published: October 2008

There are n jobs that have to be processed on one available machine. The ith job arrives at epoch r1 and it takes P1 units of time to carry out its operation. No preemptions are allowed. It is desired to minimize total flow time. A probabilistic analysis is presented for this NP-hard problem (known as 1/rj/∑Cj in the scheduling literature). Under very general probability distributions of the problem data, it is shown that the problem can be broken into 2 categories: the undersaturated and the oversaturated case. Asymptotically optimal algorithms are presented for each case.
Necessary Conditions for the Bolza Problem
Authors: Frankowska Halina
Published: October 2008

In this paper we provide necessary conditions for the Bolza problem which are obtained by using a generalization of Frechet derivative and by reducing the original problem to a convex problem. The investigation of this convex problem is carried out by approximating the given functions by smooth ones.
The Partial Order of a Polymatroid Extreme Point
Authors: Bixby R. E. , Cunningham W. H. , Topkis D. M.
Published: October 2008

Given a (polymatroid) rank function f and its corresponding polymatroid P(f), we associate with each extreme point of P(f) a certain partial order. We show that this partial order is efficiently constructible, and that it characterizes all the orderings with which the greedy algorithm can be used to generate the given extreme point. We give several applications, including one to the still open problem of finding an efficient combinatorial procedure for testing membership in polymatroids. Our results can also be applied to convex games.
Integral Polyhedra in Three Space
Authors: Scarf Herbert E.
Published: October 2008

In a series of recent papers I have introduced a particular class of convex polyhedra in Rn, arising in the study of integer programming problems with n variables. In the present paper a detailed analysis of these polyhedra will be given for the case in which n = 3; the analysis is based on an unpublished theorem demonstrated several years ago by Roger Howe, which seems to have no immediate generalization to higher values of n.
Scarf's Procedure for Integer Programming and a Dual Simplex Algorithm
Authors: White Philip M. , Caplin Andrew S. , van der Heyden Ludo
Published: October 2008

Scarf has recently introduced an algorithm for integer programs based on the combinatorial concept of primitive set. We show that as the decision variables of the integer program become continuous and the integer program reduces to a linear program, the Scarf algorithm converges to a dual simplex algorithm for the limit linear programming problem. This result is robust in the sense that even before the limit is reached, the dual simplex path is contained in the path of primitive sets generated by the Scarf algorithm.
Existence of Overtaking Optimal Trajectories for Problems with Convex Integrands
Authors: Leizarowitz Arie
Published: October 2008

In this work we study the existence of optimal overtaking trajectories for autonomous control systems on an infinite time interval. We extend, in two directions, the research initiated by Brock and Haurie (Brock, W. A., A. Haurie. 1976. On existence of overtaking optimal trajectories over an infinite time horizon. Math. Oper. Res. 1 337–346.). First we relax the technical assumptions needed to establish the existence of overtaking optimal trajectories. The assumptions in our existence result are basically those made in (Brock, W. A., A. Haurie. 1976. On existence of overtaking optimal trajectories over an infinite time horizon. Math. Oper. Res. 1 337–346.) for the existence of weakly overtaking optimal trajectories, with the additional assumption that a certain linear differential equation determined by the integrand has no nontrivial periodic solutions. A discussion and an example concerning this assumption are provided. In particular we show that this property is generic in the epi-convergence topology. Secondly, we consider convex integrands which grow uniformly to infinity rather than integrands with compact domains.
On Shortest Paths in Graphs with Random Weights
Authors: Hassin Refael , Zemel Eitan
Published: October 2008

We consider the shortest paths between all pairs of nodes in a directed or undirected complete graph with edge lengths which are uniformly and independently distributed in [0, 1]. We show that die longest of these paths is bounded by c log n/n almost surely, where c is a constant and n is the number of nodes. Our bound is the best possible up to a constant. We apply this result to some well-known problems and obtain several algorithmic improvements over existing results. Our results hold with obvious modifications to random (as opposed to complete) graphs and to any distribution of weights whose density is positive and bounded from below at a neighborhood of zero. As a corollary of our proof we get a new result concerning the diameter of random graphs.
Cores of Tangent Cones and Clarke's Tangent Cone
Authors: Martin D. H. , Watkins G. G.
Published: October 2008

It is known that Clarke's tangent cone at any point of any subset of Rn is always both unique and convex. By contrast, nearly all other notions of convex tangent cone in the literature are monotone in the sense that if a convex cone K is a tangent cone at a point x0 of a set C ⊆ Rn, then K′ ⊆ K, C ⊆ C′ automatically implies that K′ is a tangent cone of the same type for C′ at x0. This carries the rider that such tangent cones are not unique and, in general, even maximal (convex) tangent cones are not unique.

In this paper it is shown that for most monotone types, one can identify preferred tangent cones (for C at x0), called core tangent cones of that type, such that maximal core tangent cones are unique and convex.
Analysis of Heuristics for Two-Machine Flow-Shop Sequencing Subject to Release Dates
Authors: Potts C. N.
Published: October 2008

The two-machine flow-shop problem is considered in which each job becomes available for processing at its release date after which it must be processed without preemption on the first machine and then on the second machine. The objective is to minimize the maximum completion time. Three heuristics are presented which each have a worst-case performance ratio of 2. One of these is modified to give an improved worst-case performance ratio of 5/3.
Continuous-Time Red and Black: How to Control a Diffusion to a Goal
Authors: Pestien Victor C. , Sudderth William D.
Published: October 2008

A player starts at x in (0, 1) and tries to reach 1. The process (Xt, t ≥ 0) of his positions moves according to a diffusion process (or, more generally, an Ito process) whose infinitesimal parameters μ, σ are chosen by the player at each instant of time from a set depending on his current position. To maximize the probability of reaching 1, the player should choose the parameters so as to maximize μ/σ2, at least when the maximum is achieved by bounded, measurable functions. This implies that bold (timid) play is optimal for subfair (superfair), continuous-time red-and-black. Furthermore, in superfair red-and-black, the strategy which maximizes the drift coefficient of {log Xt} minimizes the expected time to reach 1.
Explicit Solution of a Two-Dimensional Deterministic Inventory Problem
Authors: Sulem Agnès
Published: October 2008

We determine the optimal ordering policy for impulse control of a deterministic two-product inventory system subject to constant demand rates, linear storage and shortage costs and economies of joint ordering. The optimal cost is explicitly obtained as the smoothest solution of a two-dimensional Quasi-Variational Inequality. Exact construction of the boundary of the continuation set leads to the optimal ordering policy. Extensions to independent products, average cost and n-product case (n > 2) are also briefly considered.
On Repeated Games with Complete Information
Authors: Sorin Sylvain
Published: October 2008

We consider N person repeated games with complete information and standard signalling. We first prove several properties of the sets of feasible payoffs and Nash equilibrium payoffs for the n-stage game and for the λ-discounted game. In the second part we determine the set of equilibrium payoffs for the Prisoner's Dilemma corresponding to the critical value of the discount factor.
Linear Programming for Finite State Multi-Armed Bandit Problems
Authors: Chen Yih Ren , Katehakis Michael N.
Published: October 2008

We consider the multi-armed bandit problem. We show that when the state space is finite the computation of the dynamic allocation indices can be handled by linear programming methods.
A Note on M. N. Katehakis' and Y.-R. Chen's Computation of the Gittins Index
Authors: Kallenberg Lodewijk C. M.
Published: October 2008

In a recent paper Katehakis and Chen propose a sequence of linear programs for the computation of the Gittins indices. If there are N projects and project v has Kv states, then ∑v=1N Kv linear programs have to be solved. In this note it is shown that instead of the Kv linear programs for project v also one parametric linear program with the same dimensions can be solved.
Optimal Consecutive-2-Out-of-n Systems
Authors: Du D. Z. , Hwang F. K.
Published: October 2008

A consecutive-2-out-of-n cycle (line) is a system of n items ordered into a cycle (line) such that the system fails if and only if two consecutive items both fail. A double-loop ring network for computers is such a cyclic system when the computers are also connected by a second loop which skips every other computer in the cycle (if n is even, there are two half loops). Suppose that item Ii works with probability Pi and that the items have been indexed so that P1 ≤ P2 ≤ ⋯ ≤ Pn. Suppose further that any permutation of the n items constitutes a system. It has been conjectured that the cyclic system [Formula: see text] minimizes the probability of failure over all such arrangements and that the line system Ln* = I1InI3In−2 … In−3I4In−1I2 minimizes the probability of failure over all arrangements of the items into a line (the line conjecture follows from the cycle conjecture by setting Pn = 1). In this paper we prove the cycle conjecture.
Envelopes and Geometrical Covers of Side-Payment Games and Their Market Representations
Authors: Artzner P. , D'Aspremont C. , Gerard-Varet L. A.
Published: October 2008

This paper deals with issues concerning the core as a solution concept for games in coalitional form as well as the use of these games in representing economies of a certain formal type. Side-payment games are imbedded in the more general class of no-side-payment games. It is shown that to a given side-payment game having an empty core one may associate two different no-side-payment games with the same (nonempty) core: the “envelope” and the “geometrical cover.” The discrepancy is explained in terms of market games.
Polyhedral Combinatorics and Network Reliability
Authors: Provan J. Scott
Published: October 2008

This paper studies the reliability of systems comprised of variables which must satisfy a set of linear equalities and nonnegativity constraints, and which are subject to random failure. A major example, which will be given special emphasis, is the reachability (source-to-all connectedness reliability) problem for stochastic networks. We show how properties of convex polyhedra, and their network counterparts, are useful in determining properties of the reliability polynomial for these systems. In particular, we show how recent results by Stanley and by Billera and Lee concerning the face numbers of convex polytopes and polyhedra can be applied to provide good upper and lower bounds on reliability in linear systems, and we apply these bounds in the network examples.
An Axiomatic Model of Unbounded Utility Functions
Authors: Toulet Claude
Published: October 2008

Savage's theory of qualitative personal probabilities leads to a representation of preferences by bounded utility functions. It is possible to relieve boundedness by relaxing the too strong hypothesis of a complete ordering among the decisions. Such an attempt has already been made for objective probabilities. This paper presents an axiomatic model of decision, inspired by Savage's point of view, which enables one to include in the theory unbounded utility functions, frequently used in concrete situations of decision.
Approximation to Optimization Problems: An Elementary Review
Authors: Kall Peter
Published: October 2008

During the last two decades the concept of epi-convergence was introduced and then was used in various investigations in optimization and related areas. The aim of this review is to show in an elementary way how closely the arguments in the epi-convergence approach are related to those of the classical theory of convergence of functions.
An Inventory Model with Limited Production Capacity and Uncertain Demands I. The Average-Cost Criterion
Authors: Federgruen A. , Zipkin P.
Published: October 2008

This paper considers a single-item, periodic-review inventory model with uncertain demands. In contrast to prior treatments of this problem we assume a finite production capacity per period. Assuming stationary data, a convex one-period cost function and a discrete demand distribution, we show (under a few additional unrestrictive assumptions) that a modified base-stock policy is optimal under the average-cost criterion; in addition, we characterize the optimal base-stock level.
An Inventory Model with Limited Production Capacity and Uncertain Demands II. The Discounted-Cost Criterion
Authors: Federgruen A. , Zipkin P.
Published: October 2008

This paper considers a single-item, periodic-review inventory model with uncertain demands. We assume a finite production capacity in each period. With stationary data, a convex one-period cost function and a continuous demand distribution, we show (under a few additional unrestrictive assumptions) that a modified basic-stock policy is optimal under the discounted cost criterion, both for finite and infinite planning horizons. In addition we characterize the optimal base-stock levels in several ways.
Explicit Solution of a General Consumption/Investment Problem
Authors: Karatzas Ioannis , Lehoczky John P. , Sethi Suresh P. , Shreve Steven E.
Published: October 2008

This paper solves a general consumption and investment decision problem in closed form. An investor seeks to maximize total expected discounted utility of consumption. There are N distinct risky investments, modelled by dependent geometric Brownian motion processes, and one riskless (deterministic) investment. The analysis allows for a general utility function and general rates of return. The model and analysis take into consideration the inherent nonnegativity of consumption and consider bankruptcy, so this paper generalizes many of the results of Lehoczky, Sethi, and Shreve (Lehoczky, J., S. Sethi, S. Shreva. 1983. Optimal consumption and investment policies allowing consumption constraints and bankruptcy. Math. Oper. Res. 8 613–636.). The value function is determined explicitly, as are the optimal consumption and investment policies. The analysis is extended to consider more general risky investments. Under certain conditions, the value functions derived for geometric Brownian motion are shown to provide upper and lower bounds on the value functions in the more general context.
Measure-Based Values of Nonatomic Games
Authors: Monderer Dov
Published: October 2008

A complete characterization of μ-symmetric linear continuous operators from pNA(μ) to FA is given. This is used to prove the existence of a unique μ-value on pNA(μ), and to deduce the general form of a μ-semivalue and the general form of a degenerate μ-value.
Probabilistic Algorithm for the Directed Traveling Salesman Problem
Authors: Steele J. Michael
Published: October 2008

A model is given for a random directed traveling salesman problem (DTSP). The asymptotic behavior of the optimal solution of the DTSP is determined, and this result is used to establish an ϵ-optimal probabilistic algorithm for solving the DTSP in polynomial time.
A Note on Positive Dynamic Programming
Authors: Van Dawen Rolf
Published: October 2008

This note considers total reward Markov decision processes with countable state space. For these models it is well known that in the positive case, i.e. the immediate reward function is nonnegative, without further conditions (1) the value iteration holds and (2) there exist pointwise good stationary strategies. Here we show that (1) remains true if the nonnegativity of the immediate reward function is replaced by the nonnegativity of the value function and that (2) remains true if there exists a strategy with nonnegative total rewards.
On the Convergence in Distribution of Measurable Multifunctions (Random Sets) Normal Integrands, Stochastic Processes and Stochastic Infima
Authors: Salinetti Gabriella , Wets Roger J.-B.
Published: October 2008

The concept of the distribution function of a closed-valued measurable multifunction is introduced and used to study the convergence in distribution of sequences of multifunctions and the epi-convergence in distribution of normal integrands and stochastic processes; in particular various compactness criteria are exhibited. The connections with the classical convergence theory for stochastic processes are analyzed and for purposes of illustration we apply the theory to sketch out a modified derivation of Donsker's Theorem (Brownian motion as a limit of normalized random walks). We also suggest the potential application of the theory to the study of the convergence of stochastic infima.
On the Convergence in Probability of Random Sets (Measurable Multifunctions)
Authors: Salinetti G. , Vervaat W. , Wets R. J.-B.
Published: October 2008

It is shown that the convergence in probability of random sets introduced by Salinetti and Wets is consistent with the more standard definitions of convergence in probability, and is metric invariant.
An Upper Bound Theorem for Polytope Pairs
Authors: Barnette D. , Kleinschmidt P. , Lee C. W.
Published: October 2008

Assume P* is a simple, convex, d-polytope with ν facets, and F* is a simple, convex d′-polytope with ν′ facets, where 0 ≤ d′ ≤ d − 1. If F* is in fact a face of P* we call (P*, F*) a polytope pair of type (d, ν, d′, ν′). Define Q* to be P* ∼ F*, the unbounded, simple d-polyhedron obtained by applying a protective transformation that sends a supporting hyperplane for F* onto the hyperplane at infinity. In this paper we answer the question: What are the maximum possible numbers of faces of different dimensions that P* and Q* can have? We restate and solve the problem in a dual, simplicial context.
The Queue M|G|1 with Markov Modulated Arrivals and Services
Authors: Regterschot G. J. K. , de Smit J. H. A.
Published: October 2008

We study an M|G|1 queue in which both the arrival rate and the service time distribution depend on the state of an underlying finite-state Markov chain. The solution is obtained by a matrix factorization method. This leads to results for waiting times and queue lengths both at arrival epochs and in continuous time. A numerical algorithm for the calculation of several quantities of interest is described and some numerical examples are given.
On the Existence of Easy Initial States for Undiscounted Stochastic Games
Authors: Tijs S. H. , Vrieze O. J.
Published: October 2008

This paper deals with undiscounted infinite stage two-person zero-sum stochastic games with finite state and action spaces. It was recently shown that such games possess a value. But in general there are no optimal strategies. We prove that for each player there exists a nonempty set of easy initial states, i.e., starting states for which the player possesses an optimal stationary strategy. This result is proved with the aid of facts derived by Bewley and Kohlberg for the limit discount equation for stochastic games.
Clique Tree Inequalities and the Symmetric Travelling Salesman Problem
Authors: Grötschel M. , Pulleyblank W. R.
Published: October 2008

The linear programming cutting plane approach for solving the travelling salesman problem has recently proven to be highly successful, cf. Crowder and Padberg (Crowder, H. P., M. W. Padberg. 1980. Solving large-scale symmetric travelling salesman problems to optimality. Management Sci. 26 495–509.), Grötschel (Grötschel, M. 1980a. On the symmetric travelling salesman problem: Solution of a 120 city problem. Math. Programming Stud. 12 61–77.), Padberg and Hong (Padberg, M. W., S. Hong. 1980. On the symmetric travelling salesman problem: A computational study. Math. Programming Stud. 12 78–107.). One of the reasons for this success is certainly the fact that instead of ordinary cutting planes (Gomory-cuts etc.) problem-specific cutting planes could be used which define facets of the underlying integer programming polytopes.

In this paper we shall define a new class of inequalities (clique tree inequalities) valid for the travelling salesman polytope which properly contains many of the known classes of inequalities (like subtour elimination constraints, 2-matching constraints, comb inequalities), and we show that all these new inequalities induce facets of the travelling salesman polytope. Since the general structure of these new inequalities is quite simple we hope that it will be possible to use the inequalities efficiently in cutting plane procedures for the travelling salesman problem.
Optimal Stopping in Sequential Games With or Without a Constraint of Always Terminating
Authors: Ohtsubo Yoshio
Published: October 2008

Zero-sum sequential games where both control variables are stopping times are considered. Two game problems are dealt with: (𝒢1) is a problem in which the players are allowed the possibility of not stopping the game, and in the other (𝒢2) they are obliged to stop the observed process at some finite (but not preassigned) time. The problem (𝒢1) is well known. In the present paper we mainly investigate (𝒢2) as compared with (𝒢1). We give sufficient conditions for the game problem (𝒢2) to have a value which is consequently equal to that of (𝒢1) and, in parallel with it, present the constructive algorithm of the value in the natural form. The saddle point in each problem is found under a certain condition. The monotone case and the Markov case are finally investigated as the special cases.
A Parametric Subproblem for Dual Methods in Decomposition
Authors: Ho James K.
Published: October 2008

The Dantzig-Wolfe decomposition algorithm for a linear program can be regarded as the primal simplex method applied to the equivalent extremal problem. If the dual simplex method is used, the subproblems will have linear fractional objectives. Abadie and Williams showed how such subproblems can be solved as a sequence of distinct linear programs. This paper proposes to obtain the same results using a single parametric linear program which means that such special subproblems can be handled by a general purpose algorithm. The procedure should, therefore, greatly improve the practicality of postoptimality and parametric analysis using decomposition.
The Jacobian Matrix, Global Univalence and Completely Mixed Games
Authors: Parthasarathy T. , Ravindran G.
Published: October 2008

In this paper we prove global univalence results in R4 when the Jacobian matrices are of the Leontief type. Proofs of these make use of ideas from Gale-Nikaido and some nice game theoretic results on completely mixed games due to Kaplansky.
Computing Bounds for Stochastic Programming Problems by Means of a Generalized Moment Problem
Authors: Birge John R. , Wets Roger J.-B.
Published: October 2008

Bounds on the expected value of a convex function are obtained by means of an approximating generalized moment problem. Numerical implementation is discussed in the context of stochastic programming problems.
On the Convergence of Policy Iteration in Finite State Undiscounted Markov Decision Processes: The Unichain Case
Authors: Hordijk Arie , Puterman Martin L.
Published: October 2008

We study the convergence of policy iteration for the undiscounted, finite state, discrete time Markov decision problem with compact action space and unichain transition structure. Using a “Newton Method type” representation for policy iteration, we establish the existence of a solution to the optimality equation. We show that to find an average optimal policy, it is sufficient to solve the optimality equation on the recurrent set of the maximizing policy. Under the additional assumption of a unique maximizing policy at each stage of the policy iteration procedure, we show that the iterates are convergent and the resulting policy is Blackwell optimal.
Martingale Inequalities and NP-Complete Problems
Authors: Rhee Wansoo T. , Talagrand Michel
Published: October 2008

We use martingale inequalities in the probabilistic analysis of stochastic models of NP-complete problems. We give examples of applications to the Bin Packing and Traveling-Salesman Problems. In both cases, we obtain sharp bounds on Pr(|Un − EUn| > t), where Un is the objective function value of the problem with n random data.
Corrigenda: Clique Tree Inequalities and the Symmetric Travelling Salesman Problem
Authors: Grötschel M. , Pulleyblank W. R.
Published: October 2008

Due to an editorial oversight, in our paper published in Vol. 11, Number 4 (November 1986), the following pages should now follow journal page 553 and precede 554. (Also note pages 556 and 557 should be omitted from their position in the printed edition.
Structured Policies for a Sequential Design Problem with General Distributions
Authors: Benzing Harald , Kolonko Michael
Published: October 2008

Consider the problem of allocating two treatments in a sequence of N trials such that the total expected reward is maximized. We assume that the distribution of outcomes is known for one of the treatments only (so-called one-armed bandit problem).

In a suitable dynamic programming model we examine the structural properties of an optimal policy. In particular we extend results known for Bernoulli distributed outcomes to more general distributions.

Our main technical results are monotonicity and convexity of the total expected reward.
Linear Systems for Constrained Matching Problems
Authors: Cook W. , Pulleyblank W. R.
Published: October 2008

Each polyhedron of full dimension has a unique (up to positive scalar multiples of the inequalities) minimal defining system and a unique minimal totally dual integral defining system with integer left hand sides. These two minimal systems are characterised for the convex hull of the simple b-matchings of a graph. These characterisations are then used to provide similar characterisations for the convex hull of matchings, b-matchings, and capacitated b-matchings. Each of these characterisations gives a “best possible” min-max relation for the corresponding combinatorial objects.
Semivalues of Simple Games
Authors: Einy Ezra
Published: October 2008

It is shown that each semivalue (bounded semivalue) on the class SG of monotonic simple games with a finite support can be uniquely extended to a semivalue (continuous semivalue) on the class G of all games with a finite support. We use this to show that the formula that is given for semivalues (continuous semivalues) on G by Dubey, Neyman and Weber also holds for semivalues (bounded semivalues) on SG. We also derive another formula for semivalues on SG (in terms of the minimal winning coalitions of the game).
Some New Matroids on Graphs: Cut Sets and the Max Cut Problem
Authors: Conforti Michele , Rao M. R.
Published: October 2008

We define some new matroids on the edge set of a graph. We show that minimal disconnecting edge sets and minimal edge sets which cover all the odd cycles are cocircuits of a binary matroid. We give a polynomial algorithm for finding a minimum weight circuit in our matroids. A necessary and sufficient condition for an edge set to be the minimum weight odd cycle cover is derived in terms of the family of cut sets of the graph.
On the Complexity of the Elzinga-Hearn Algorithm for the 1-Center Problem
Authors: Drezner Zvi , Shelah Saharon
Published: October 2008

We show that the complexity of the Elzinga-Hearn algorithm for the 1-center (single facility minimax) problem is Ω(n2). We also show that the algorithm reaches a solution within any given accuracy in O(n) time.
Homogeneous Games: Recursive Structure and Computation
Authors: Rosenmüller Joachim
Published: October 2008

The structure of a homogeneous weighted majority game (in general not constant-sum) is analyzed via the concepts of characters of types and of satellite games being played by smaller players in order to replace larger ones. Two proofs for the existence of the minimal representation (see Ostmann [Ostmann, A. On the Minimal Representation of Homogeneous Games. Internal. J. Game Theory (to appear).]) are given. An algorithm to construct the satellite games, the characters and the minimal representation directly from any homogeneous representation is described.
On the Solution Value of the Continuous p-Center Location Problem on a Graph
Authors: Tamir Arie
Published: October 2008

Let G = (V, E) be an undirected graph with positive edge lengths. Let rp denote the solution value to the continuous p-center location problem on G. We prove that rp is of the form rp = T/2q, where T is the length of an Euler tour of a subgraph of G which belongs to one of four possible types, and q is an integer, 1 ≤ q ≤ 2p. We also discuss algorithmic implications of this result.
Minkowski's Convex Body Theorem and Integer Programming
Authors: Kannan Ravi
Published: October 2008

The paper presents an algorithm for solving Integer Programming problems whose running time depends on the number n of variables as nO(n). This is done by reducing an n variable problem to (2n)5i/2 problems in n − i variables for some i greater than zero chosen by the algorithm. The factor of O(n5/2) “per variable” improves the best previously known factor which is exponential in n. Minkowski's Convex Body theorem and other results from Geometry of Numbers play a crucial role in the algorithm. Several related algorithms for lattice problems are presented. The complexity of these problems with respect to polynomial-time reducibilities is studied.