bluuebunny/crossref_metadata_2025 huggingface dataset:
Closed Form Two-Sided Bounds for Probabilities that At Least r and Exactly r Out of n Events Occur
Authors: Boros Endre , Prékopa András
Published: October 2008

In two previous papers Prékopa (Prékopa, A. 1986a. Boole-Bonferroni inequalities and linear programming. Oper. Res. 36 145–162; Prékopa, A. 1986b. Sharp bounds on probabilities using linear programming. To appear in Oper. Res.) gave algorithms to approximate probabilities that at least r and exactly r out of n events occur (1 ≤ r ≤ n). Primal and dual linear programming problems were formulated and solved by dual type algorithms. The purpose of the present paper is to give closed forms for the basis inverse and the corresponding dual vector in case of an arbitrary basis, furthermore to give closed forms for the lower and upper bounds, approximating the probability in question, in case of a dual feasible basis. In the case when the probability that at least one out of n events occurs is approximated, it is shown that the absolute values of the components of any dual vector form a monotonically decreasing sequence. The paper improves the method of inclusion-exclusion, proves new probability inequalities and proves the sharpness of some known inequalities.
Change of Life Distribution Via a Hazard Transformation: An Inequality with Application to Minimal Repair
Authors: Arjas E. , Norros I.
Published: October 2008

We introduce a general transformation of hazard rates and discuss the corresponding change of a life length distribution. Minimal repair transformations are shown to be special cases of this framework which builds on general results concerning likelihood ratios for point processes, and in particular on the Girsanov theorem for point processes. We then study the role of the available information and the consequent definition of “state” in the change of distributions. By using the general notion of F-minimal repair, where F stands for the information which identifies the state of the considered device, we show that the “black box”-minimal repair modeling leads to a stochastically longer total life length than the more realistic one based on internal state information. Thus the former forms a potential source of bias in minimal repair modeling.
Second-Order Optimality Conditions in Nonlinear Programming Obtained by Way of Epi-Derivatives
Authors: Rockafellar R. Tyrrell
Published: October 2008

Dedicated to the memory of Robin W. Chaney

Second-order optimality conditions for finite-dimensional smooth and nonsmooth nonlinear programming are obtained by a new method that emphasizes a close connection with geometrical approximation of the essential objective function. The approximation is secured by the use of certain epi-derivatives defined by epiconvergence. The optimality conditions are expressed in a form that covers general interval constraints and their possible representation through penalties or an augmented Lagrangian. An abstract constraint involving restriction to a convex polyhedron is incorporated.
Infinite Horizon Optimization
Authors: Schochetman Irwin E. , Smith Robert L.
Published: October 2008

We consider the general problem of choosing a discounted cost minimizing infinite sequence of decisions from a closed subset of the product space formed by a sequence of arbitrary compact metric spaces. Examples include equipment replacement, production planning and, more generally, infinite stage mathematical programs. It is shown that the optimal costs for finite horizon approximating problems converge to the optimal infinite horizon cost as the horizons diverge to infinity. Moreover, the existence of a unique algorithmically optimal (i.e. accumulation point) solution is shown to be a necessary and sufficient condition for convergence in the product topology (i.e. policy convergence) of all finite horizon optima. Under the weaker condition of Hausdorff convergence of the sets of finite horizon optima to the set of infinite horizon optima, we show how to force policy convergence through a natural tie-breaking rule. Finally, a forward algorithm is presented which, in the presence of a unique infinite horizon optimum, is guaranteed to converge.
Stable Equilibria—A Reformulation
Authors: Mertens Jean-François
Published: October 2008

A reformulation of stable equilibria is given, yielding a number of additional properties like backwards induction while still giving “typically,” i.e., except in “made up” examples, the same solutions.
On the Status Quo Sets Induced by the Raiffa Solution to the Two-Person Bargaining Problem
Authors: Livne Zvi A.
Published: October 2008

We prove that the status quo sets induced by the Raiffa Solution to the two-person Bargaining Problem are curves, except when the bargaining domain is rectangular. This property is used in a separate paper by Livne (Livne, Z. 1987. Axiomatic characterization at the Raiffa solution to the Nash bargaining problem. Columbia Business School. Forthcoming in Oper. Res.) in the axiomatization of the Raiffa Solution.
An Existence Theorem in Vector Optimization
Authors: Luc Dinh The
Published: October 2008

Dedicated to Professor Andras Prekopa on his sixtieth birthday

A general theorem which covers several recent known results on the existence of efficient solutions is established for vector optimization problems in infinite-dimensional spaces with arbitrary ordering cones.
Easily Computable Facets of the Knapsack Polytope
Authors: Zemel Eitan
Published: October 2008

It is known that facets and valid inequalities for the knapsack polytope P can be obtained by lifting a simple inequality derived from each minimal cover. We study the computational complexity of such lifting. In particular, we show that the task of computing a lifted facet can be accomplished in O(ns) where s ≤ n is the cardinality of the minimal cover. Also, for a lifted inequality with integer coefficients, we show that the dual tasks of recognizing whether the inequality is valid for P or is a facet of P can be done within the same time bound.
Reneging from Processor Sharing Systems and Random Queues
Authors: Assaf David , Haviv Moshe
Published: October 2008

In a memoryless processor sharing system and in a memoryless random queue, both with some cost structure, it is shown that there exists an ε-Nash equilibrium symmetric reneging strategy which is Markovian and stationary with respect to the queue length and which is of the following (N*, θ*, η(ε)) form: (i) stay in the system when the queue size is smaller than some specified critical level N*; (ii) randomly renege with constant specified rate θ* when the queue size is N*; (iii) randomly renege with large enough rate ηn(ε) when the queue size is n with n>N*. Moreover, for all n with n>N*, limε→ 0ηn(ε)=∞. On the other hand, N* and θ* are not functions of ε and they depend only on the parameters defining the system. Finally, a stationary and Markovian symmetric Nash equilibrium strategy does not exist.
One-Dependent Regenerative Processes and Queues in Continuous Time
Authors: Sigman Karl
Published: October 2008

Motivated by the study of queues in continuous time, a “one-dependent” regenerative process is defined and its ergodic properties are given. We show that a continuous time Harris recurrent Markov process (HRMP) is of this type and give a different proof of the ergodic properties of HRMP's based on this fact. We next introduce the new notion of a marked point process (mpp) governed by a HRMP and by doing so obtain a class of mpp's that are one-dependent regenerative. This class is shown to include the superposition of independent renewal processes, the departure process from a FIFO GI/GI/c queue, Markov modulated arrivals and the loss stream (overflow) from a GI/GI/1/0 queue. We also present a general framework for representing queues in continuous time as HRMP's when the input is a mpp governed by a HRMP and thus obtain a continuous time analogue of [20]. In this context we consider a single server queue with feedback and a tandem queue. Finally, due to the potential for regenerative type simulation, we state a CLT for one-dependent regenerative processes.
An Algorithm for Convex Quadratic Programming That Requires O(n3.5L) Arithmetic Operations
Authors: Mehrotra Sanjay , Sun Jie
Published: October 2008

A new interior point method for minimizing a convex quadratic function over a polytope is developed. We show that our method requires O(n3.5L) arithmetic operations. In our algorithm we construct a sequence Pz0, Pz1, …, Pzk, … of nested convex sets that shrink towards the set of optimal solution(s). During iteration k we take a partial Newton step to move from an approximate analytic center of Pzk − 1 to an approximate analytic center of Pzk. A system of linear equations is solved at each iteration to find the step direction. The solution that is available after O(√mL) iterations can be converted to an optimal solution. Our analysis indicates that inexact solutions to the linear system of equations could be used in implementing this algorithm.
Finding Minimum-Cost Circulations by Successive Approximation
Authors: Goldberg Andrew V. , Tarjan Robert E.
Published: October 2008

We develop a new approach to solving minimum-cost circulation problems. Our approach combines methods for solving the maximum flow problem with successive approximation techniques based on cost scaling. We measure the accuracy of a solution by the amount that the complementary slackness conditions are violated.

We propose a simple minimum-cost circulation algorithm, one version of which runs in O(n3log(nC)) time on an n-vertex network with integer arc costs of absolute value at most C. By incorporating sophisticated data structures into the algorithm, we obtain a time bound of O(nm log(n2/m)log(nC)) on a network with m arcs. A slightly different use of our approach shows that a minimum-cost circulation can be computed by solving a sequence of O(n log(nC)) blocking flow problems. A corollary of this result is an O(n2(log n)log(nC))-time, m-processor parallel minimum-cost circulation algorithm. Our approach also yields strongly polynomial minimum-cost circulation algorithms.

Our results provide evidence that the minimum-cost circulation problem is not much harder than the maximum flow problem. We believe that a suitable implementation of our method will perform extremely well in practice.
Minimizing Total Tardiness on One Machine is NP-Hard
Authors: Du Jianzhong , Leung Joseph Y.-T.
Published: October 2008

The problem of minimizing the total tardiness for a set of independent jobs on one machine is considered. Lawler has given a pseudo-polynomial-time algorithm to solve this problem. In spite of extensive research efforts for more than a decade, the question of whether it can be solved in polynomial time or it is NP-hard (in the ordinary sense) remained open. In this paper the problem is shown to be NP-hard (in the ordinary sense).
Recovering Optimal Basic Variables in Karmarkar's Polynomial Algorithm for Linear Programming
Authors: Ye Yinyu
Published: October 2008

Primal-slack ellipsoids are described which contain all of the optimal primal feasible solutions in a standard form variant of Karmarkar's projective algorithm for linear programming (LP). Using these ellipsoids, we show how to identify optimal basic variables using few additional arithmetic operations and also simultaneously reduce the size of the LP problem during the course of the algorithm. Some preliminary computational experiments are given which compare different stopping criteria.
On Quasi-Convex Duality
Authors: Penot Jean-Paul , Volle Michel
Published: October 2008

The familiar Fenchel-Moreau-Rockafellar duality scheme deduced from a conjugation is shown to be applicable to quasi-convex problems. Here quasi-affine functions take the place of affine functions. The links with other quasi-convex dualities are examined.
Continuous-Time Flows in Networks
Authors: Philpott A. B.
Published: October 2008

We consider a class of maximum flow problems formulated in a directed network where the arc flows vary as Lebesgue-measurable functions of time, and storage is allowed at the nodes of the network. A max flow-min cut result of Anderson, Nash and Philpott [1] is extended to cover the case where each arc has a traversal time. The ideas of the paper are then applied to derive some simple results on emptying networks at least cost.
Portfolio Selection with Transaction Costs
Authors: Davis M. H. A. , Norman A. R.
Published: October 2008

In this paper, optimal consumption and investment decisions are studied for an investor who has available a bank account paying a fixed rate of interest and a stock whose price is a log-normal diffusion. This problem was solved by Merton and others when transactions between bank and stock are costless. Here we suppose that there are charges on all transactions equal to a fixed percentage of the amount transacted. It is shown that the optimal buying and selling policies are the local times of the two-dimensional process of bank and stock holdings at the boundaries of a wedge-shaped region which is determined by the solution of a nonlinear free boundary problem. An algorithm for solving the free boundary problem is given.
Stochastic Analysis of a Modified First Fit Decreasing Packing
Authors: Rhee Wansoo T.
Published: October 2008

We make a stochastic analysis of a modified version mFFD of First Fit Decreasing, in which each bin is closed after it receives its first fallback item. Consider a probability measure μ on [0, 1], and independent random variables X1, …, Xn distributed according to μ. Let Rn = R(X1, …, Xn) be the number of unit size bins that mFFD needs to pack items of size X1, …, Xn. We prove that c(μ) = limn→∞ E(Rn)/n exists and that the random variable (Rn − nc(μ))/√n converges in distribution. The main tools are deterministic inequalities concerning mFFD, that might be of independent interest.
Max-Balancing Weighted Directed Graphs and Matrix Scaling
Authors: Schneider Hans , Schneider Michael H.
Published: October 2008

A weighted directed graph G is a triple (V, A, g) where (V, A) is a directed graph and g is an arbitrary real-valued function defined on the arc set A. Let G be a strongly-connected, simple weighted directed graph. We say that G is max-balanced if for every nontrivial subset of the vertices W, the maximum weight over arcs leaving W equals the maximum weight over arcs entering W. We show that there exists a (up to an additive constant) unique potential pv for v ∈ V such that (V, A, gp) is max-balanced where gap = pu + ga − pv for a = (u, v) ∈ A. We describe an O(|V|2|A|) algorithm for computing p using an algorithm for computing the maximum cycle-mean of G. Finally, we apply our principal result to the similarity scaling of nonnegative matrices.
Efficiency of the Primal Network Simplex Algorithm for the Minimum-Cost Circulation Problem
Authors: Tarjan Robert E.
Published: October 2008

We study the number of pivots required by the primal network simplex algorithm to solve the minimum-cost circulation problem. We propose a pivot selection rule with a bound of n(logn)/2+O(1) on the number of pivots, for an n-vertex network. This is the first known subexponential bound. The network simplex algorithm with this rule can be implemented to run in n(logn)/2+O(1) time. In the special case of planar graphs, we obtain a polynomial bound on the number of pivots and the running time. We also consider the relaxation of the network simplex algorithm in which cost-increasing pivots are allowed as well as cost-decreasing ones. For this algorithm we propose a pivot selection rule with a bound of

O(nm · min{log(nC), m log n})

on the number of pivots, for a network with n vertices, m arcs, and integer arc costs bounded in magnitude by C. The total running time is

O(nm log n · min{(log nC), m log n}).

This bound is within a logarithmic factor of those of the best previously known algorithms for the minimum-cost circulation problem.
Some Generalized Max-Flow Min-Cut Problems in the Plane
Authors: Bienstock Dan
Published: October 2008

We consider variants of the max-flow min-cut problems in the plane, motivated by models of damage, where certain sets of edges of the graph can be simultaneously removed, rather than one edge at a time as in the standard min-cut problem. Our main contributions are: a polynomial algorithm for the generalized min-cut problem, an NP-completeness result for the generalized max-flow problem, and an “approximate” generalized max-flow min-cut theorem.
Characterizing the Nash and Raiffa Bargaining Solutions by Disagreement Point Axioms
Authors: Peters Hans , Van Damme Eric
Published: October 2008

We provide a new characterization of the n-person Nash bargaining solutions which does not involve Nash's Independence of Irrelevant Alternatives axiom, but mainly uses axioms which concern changes in the disagreement point and leave the feasible set fixed. The main axiom requires a convex combination of a disagreement point and the corresponding solution point to give rise to that same solution point. Further, we describe how the disagreement point approach can be applied to other bargaining solutions. The main result of the latter part is a first characterization of the so-called Continuous Raiffa solution.
Convergence of Conditional Expectations for Unbounded Random Sets, Integrands, and Integral Functionals
Authors: Hess Christian
Published: October 2008

Given a sequence of unbounded convex random sets, we study under which conditions Fatou's lemma for the weak upper limit of their conditional expectations holds. We also give multivalued versions of dominated and monotone convergence theorems, and we discuss the special case of the integral. Finally, applications to epigraphic convergence of integrands and to Mosco convergence of certain integral functionals are provided.
The Nucleolus of a Matrix Game and Other Nucleoli
Authors: Potters Jos A. M. , Tijs Stef H.
Published: October 2008

We define the nucleolus of a continuous convex map F: Π → Rm on a convex compact set Π ⊂ Rn. As special cases we obtain known notions as nucleolus, prenucleolus and weighted nucleolus of a TU-game with (or without) coalition structure. Also the nucleolus of a matrix game turns out to be an interesting special case. It appears that the nucleolus of a matrix game coincides with the set of Dresher optimal strategy pairs of the game. This implies, in particular, that the nucleolus consists of the proper equilibria of the matrix game. To each (zero-normalized) TU-game one can construct a matrix game—the excess game—such that the nucleolus of the TU-game coincides with the unique proper optimal strategy of player II in the excess game. Also for other nucleoli of TU-games a suitable matrix game can be constructed where the nucleolus under consideration is related to the nucleolus of the matrix game in an analogous way. A balancedness condition is given characterizing nucleolus elements of a matrix game. It is shown that this balancedness result implies the known balancedness characterizations of Kohlberg, Sobolev, Owen and Wallmeier.
New Partitioning Method for a Class of Nonconvex Optimization Problems
Authors: Thach Phan Thien
Published: October 2008

We consider the problem min{f(x, y): gi(x, y) ≤ 0, i = 1, …, m, x ∈ X, y ∈ Y} where f and the gi are lower semicontinuous and convex in y for fixed x but not convex jointly in (x, y), X is a compact subset of Rn, Y is a closed convex set in Rm. In order to decompose this problem into subproblems, each depending either on the x-variables alone or the y-variables alone, we propose a new partitioning method which does not require the Benders-Geoffrion's condition on the structure of joint constraints and the objective function. The relaxed master problems generated by our partitioning method are d.c programs and they can be systematically solved by recent algorithms.
Recurrence Conditions for Average and Blackwell Optimality in Denumerable State Markov Decision Chains
Authors: Dekker Rommert , Hordijk Arie
Published: October 2008

In a previous paper Dekker and Hordijk (1988) presented an operator theoretical approach for multichain Markov decision processes with a countable state space, compact action sets and unbounded rewards. Conditions were presented guaranteeing the existence of a Laurent series expansion for the discounted rewards, the existence of average and Blackwell optimal policies and the existence of solutions for the average and Blackwell optimality equations. While these assumptions were operator oriented and formulated as conditions for the deviation matrix, we will show in this paper that the same approach can also be carried out under recurrence conditions. These new conditions seem easier to check in general and are especially suited for applications in queueing models.
Generalized Semi-Markov Processes: Antimatroid Structure and Second-Order Properties
Authors: Glasserman Paul , Yao David D.
Published: October 2008

A generalized semi-Markov scheme models the structure of a discrete event system, such as a network of queues. By studying combinatorial and geometric representations of schemes we find conditions for second-order properties—convexity/concavity, sub/supermodularity—of their event epochs and event counting processes. A scheme generates a language of feasible strings of events. We show that monotonicity of the event epochs is equivalent to this language forming an antimatroid with repetition. This connection gives rise to a rich combinatorial structure, and serves as a starting point for other properties. For example, by strengthening the antimatroid condition we give several equivalent characterizations of the convexity of event epochs within a scheme. All of these correspond, in slightly different ways, to making a certain score space a lattice, to closing an ordinary antimatroid under intersections. We also establish second-order properties across schemes tied together through a synchronization mechanism. A geometric view based on the score space facilitates verification of these properties in certain queueing systems.
On the Second Optimality Equation for Semi-Markov Decision Models
Authors: Schäl Manfred
Published: October 2008

For a semi-Markov decision model with average return, the validity of the second optimality equation is shown in the (nonmodified) form where the actions run through the set of all admissible actions rather than through the set of maximum points (conserving actions) for the first optimal equation. As a consequence the existence of a strongly optimal stationary policy is shown. The results seem to be known only for finite state finite action models whereas here countable state compact action models with unbounded rewards are considered.
Strong Approximations of Open Queueing Networks
Authors: Horváth Lajos
Published: October 2008

We consider a queueing system with one or more stations. We show that the queue length processes can be approximated with Brownian motions or reflected Brownian motions. Using the approximations we obtain rates of convergence of the distributions and expected values of queue lengths.
Variability Sensitive Markov Decision Processes
Authors: Baykal-Gürsoy Melike , Ross Keith W.
Published: October 2008

Considered are time-average Markov Decision Processes (MDPs) with finite state and action spaces. Two definitions of variability are introduced, namely, the expected time-average variability and time-average expected variability. The two criteria are in general different, although they can both be employed to penalize for variance in the stream of rewards. For communicating MDPs, we construct a (randomized) stationary policy that is ε-optimal for both criteria; the policy is optimal and pure for a specific variability function. For general multichain MDPs, a state space decomposition leads to a similar result for the expected time-average variability. We also consider the problem of the decision maker choosing the initial state along with the policy.
Existence Without Explicit Compactness in Stochastic Dynamic Programming
Authors: Balder Erik J.
Published: October 2008

A new kind of existence result for stochastic dynamic programming, without explicit compactness conditions, is obtained by working with a new coercivity condition for the reward functions.
Integer Solution to Synthesis of Communication Networks
Authors: Sridhar S. , Chandrasekaran R.
Published: October 2008

This paper describes a polynomial-time algorithm for the following problem: Let ri,j be the given requirements for all i, j ∈ {1, …, n}, with ri,j = rj,i for i, j. Find integer capacities ci,j for all i, j ∈ {1, …, n} such that (considering 1, …, n as the vertices of an undirected network N, with capacities ci,j):

(i) for for all i ≠ j there exists a flow in N from i to j of value, at least ri,j;

(ii) ∑i<j ci,j is minimized.

This is the integer version of Gomory and Hu's problem to synthesize an undirected network. It is shown that rounding holds when there is no node with unit potential.
Player Type Distributions as State Variables and Information Revelation in Zero Sum Repeated Games with Discounting
Authors: Bergin James
Published: October 2008

This paper examines the role of the player type distributions in repeated zero sum games of incomplete information with discounting of payoffs. In particular the strategic “sufficiency” of the posterior distributions for histories and the limiting properties of the posterior sequence are discussed. It is shown that differentiability of the value function is sufficient to allow the posteriors to serve as “state” variables for histories.

The limiting properties of the posterior distributions are considered and a characterization given of the set of possible limit points of the posterior distribution. This characterization is given in terms of the “value” of information in the one-stage game.
Some Existence Results for Multivalued Complementarity Problems
Authors: Gowda M. Seetharama , Pang Jong-Shi
Published: October 2008

This paper presents some new results for the existence of a solution to a multivalued complementary problem. These results are derived under a “upper limiting homogeneity” (ULH) property on the multifunction defining the complementarity problem and on a certain closedness/interiority condition. The closedness condition seems to be new in the context of existence proof for the multivalued complementarity problem. We show that this closedness condition is satisfied by the class of polyhedral multifunctions.
The EPI-Distance Topology: Continuity and Stability Results with Applications to Convex Optimization Problems
Authors: Beer Gerald , Lucchetti Roberto
Published: October 2008

Let Γ(X) denote the proper, lower semicontinuous, convex functions on a Banach space X, equipped with the completely metrizable topology of uniform convergence of distance functions on bounded sets. We show, subject to some standard constraint qualifications, that the operations of addition and restriction are continuous. These results are applied to convex well-posed optimization problems, as well as to convergence of approximated solutions in infinite dimensional convex programming, to linear functionals exposing convex sets, and to metric projections. Also, for any given function in Γ(X), we obtain results regarding the convergence of its inf-convolution with smoothing kernels.
The Fixed-Outdegree 1-Arborescence Polytope
Authors: Balas Egon , Fischetti Matteo
Published: October 2008

A 1-arborescence is a spanning arborescence rooted at node 1, plus one arc incident into node 1. The 1-arborescence polytope, the convex hull of incidence vectors of 1-arborescences, is a well-known relaxation of the Asymmetric Traveling Salesman (ATS) polytope. In this paper we study the Fixed Outdegree 1-Arborescence (FDA) polytope, defined as the convex hull of incidence vectors of 1-arborescences having outdegree 1 at a prescribed subset F of nodes. The FDA polytope becomes the 1-arborescence polytope when F = ∅, and it becomes the ATS polytope when F is the entire node set. We derive several classes of valid inequalities for the FDA polytope and show that they are facet defining. This is done by using a theorem that establishes sufficient conditions for a facet defining inequality for the ATS polytope to also be facet defining for the FDA polytope. We then introduce the class of FD inequalities and show that they define facets of both the ATS polytope and the FDA polytope. Finally, we define a canonical form that facilitates rigorous comparisons between inequalities, and use it to show that the new facets are distinct from each other and from other known facets.
On Some Network Flow Games
Authors: Granot Daniel , Granot Frieda
Published: October 2008

We analyze three subclasses of cooperative games arising from network optimization problems in which the resources, such as arcs or nodes in the network, are controlled by individuals who have conflicting objectives. The first subclass of cooperative games is induced by network optimization problems over directed augmented trees. We show that for this subclass of games the kernel coincides with the nucleolus, and that the nucleolus can be characterized as the unique revenue allocation vector in which every pair of arc owners who are adjacent in the tree are located symmetrically with respect to their bargaining range. We further give a linear characterization of the core of this subclass of games, which is then used to provide a more explicit representation of the nucleolus and to construct a strongly polynomial algorithm for generating it. The second subclass of cooperative games is induced by maximum flow problems in simple undirected networks. We provide a useful parametric representation of the core of this subclass of games, which is used to characterize the nucleolus and the intersection of the core and the kernel. Explicitly, we show that the intersection of the core and the kernel consists of all revenue allocations in the core which assign equal payoffs to any pair of unseparated arc owners. We further demonstrate that among the core vectors, the nucleolus is the unique revenue allocation vector in which the smallest allocations are maximized in a lexicographical sense. The third cooperative game that we study is the assignment game, introduced by Shapley and Shubik (1972). This game is induced by the assignment problem which can be cast as a network optimization problem. We investigate the relationship between the kernel and the core of the assignment game, and provide a necessary and sufficient condition for the core to be contained in the kernel. We further show that, in general, the intersection of the kernel and the core is not a convex set. We also exhibit that under certain conditions the nucleolus has a simple characterization as the unique vector in the core in which the smallest revenue allocations are maximized in a lexicographical sense. Finally, we consider the horse market example of Bohm-Bawerk (1923), for which it is shown that the core is contained in the kernel and that the nucleolus is the midpoint of the core.
An NP-Hard Open Shop Scheduling Problem with Polynomial Average Time Complexity
Authors: Lu Lu , Posner Marc E.
Published: October 2008

While the worst-case complexity of most scheduling problems is known, the average-case complexity has not been studied. This paper examines the average-case complexity of the following NP-hard open shop scheduling problem: minimize the makespan on two machines with two distinct release dates. We present a deterministic algorithm where the average-case complexity is polynomial in the number of jobs when the known deterministic processing times of jobs are generated for each machine as nonnegative i.i.d. random variables from certain classes of distributions. The classes of distributions include all bounded distributions and all distributions with exponential tails. Linear time algorithms for two variations of the two-machine open shop scheduling problem are also obtained. These problems are minimizing the weighted sum of machine completion times, and minimizing the makespan when one machine is initially unavailable for processing. A variation of the second problem can be used to solve the problem of minimizing the makespan when there is a rolling horizon.
Existence of Interior Points and Interior Paths in Nonlinear Monotone Complementarity Problems
Authors: Güler Osman
Published: October 2008

This paper establishes basic results on the existence of interior points and interior paths in a nonlinear monotone complementarity problem in ℝn under very weak interior conditions. We show that the interior paths are bounded, continuous, and all the limit points of the paths are solutions to the complementarity problem. We prove that certain sets, including the solution set to the complementary problem, form a compact convex set. We also prove the existence of generalized interior points and interior paths. These generalized paths are also continuous and contain readily available starting points from which we can follow the paths to locate the solutions to the complementarity problem. We prove our results in the context of maximal monotone operators. The result presented here can be used to develop polynomial time interior point algorithms for general monotone complementarity problems.
Average Optimality in Dynamic Programming with General State Space
Authors: Schäl Manfred
Published: October 2008

A Markovian decision model with general state space, compact action space, and the average cost as criterion is considered. The existence of an optimal policy is shown via an optimality inequality in terms of the minimal average cost g and a relative value function w. The existence of some w is usually shown via relative compactness in a space of real-valued functions on the state space. Here it shall be shown that one can instead do with pointwise relative compactness in the set of real numbers if one makes use of a (generalized) lower limit of functions. An application to an inventory model is given.
Nonlinear Proximal Point Algorithms Using Bregman Functions, with Applications to Convex Programming
Authors: Eckstein Jonathan
Published: October 2008

A Bregman function is a strictly convex, differentiable function that induces a well-behaved distance measure or D-function on Euclidean space. This paper shows that, for every Bregman function, there exists a “nonlinear” version of the proximal point algorithm, and presents an accompanying convergence theory. Applying this generalization of the proximal point algorithm to convex programming, one obtains the D-function proximal minimization algorithm of Censor and Zenios, and a wide variety of new multiplier methods. These multiplier methods are different from those studied by Kort and Bertsekas, and include nonquadratic variations on the proximal method of multipliers.
Cut-Polytopes, Boolean Quadric Polytopes and Nonnegative Quadratic Pseudo-Boolean Functions
Authors: Boros Endre , Hammer Peter L.
Published: October 2008

In this paper we present a class of valid inequalities as well as a class of facets for the cut-polytope of the complete graph. It is shown that many of the known classes of valid inequalities, e.g., triangle, hypermetric and cycle inequalities, belong to this class. By specializing some of the parameters, large classes of facets can be defined. It is shown that each of these classes contains at least (n/3)n/3 facets, where n ≥ 10 denotes the number of vertices, and that the corresponding separation problems are polynomially solvable. These results are based on a one-to-one correspondence established between the set of valid inequalities (facets) for the cut-polytope of Kn+1, and the set of nonnegative (extremal) quadratic pseudo-Boolean functions in n variables.
Analysis of Probabilistic Combinatorial Optimization Problems in Euclidean Spaces
Authors: Jaillet Patrick
Published: October 2008

Probabilistic combinatorial optimization problems are generalized versions of deterministic combinatorial optimization problems with explicit inclusion of probabilistic elements in the problem definitions. Based on the probabilistic traveling salesman problem (PTSP) and on the probabilistic minimum spanning tree problem (PMSTP), the objective of this paper is to give a rigorous treatment of the probabilistic analysis of these problems in the plane. More specifically we present general finite-size bounds and limit theorems for the objective functions of the PTSP and PMSTP. We also discuss the practical implications of these results and indicate some open problems.
Probabilistic Analysis of Network Flow Algorithms
Authors: Karp Richard M. , Motwani Rajeev , Nisan Noam
Published: October 2008

This paper is concerned with the design and probabilistic analysis of algorithms for the maximum-flow problem and capacitated transportation problems. These algorithms run in linear time and, under certain assumptions about the probability distribution of edge capacities, obtain an optimal solution with high probability. The design of our algorithms is based on the following general method, which we call the mimicking method, for solving problems in which some of the input data are deterministic and some are random with a known distribution:

1. Replace each random variable in the problem by its expectation; this gives a deterministic problem instance that has a special form, making it particularly easy to solve;

2. Solve the resulting deterministic problem instance;

3. Taking into account the actual values of the random variables, mimic the solution of the deterministic instance to obtain a near-optimal solution to the original problem;

4. Fine-tune this suboptimal solution to obtain an optimal solution.

We present linear time algorithms to compute a feasible flow in directed and undirected capacitated transportation problem instances. The algorithms are shown to be successful with high probability when the probability distribution of the input data satisfies certain assumptions. We also consider the maximum flow problem with multiple sources and sinks. We show that with high probability the minimum cut isolates either the sources or the sinks, and we give a linear-time algorithm that produces a maximum flow with high probability.
Stochastic Machine Minimization with Constant Service Times
Authors: Coffman E. G. , Flatto Leopold , Wright Paul E.
Published: October 2008

We consider the nonpreemptive scheduling of n ≥ 1 jobs on identical, parallel machines. With job running times all given by some constant, the objective is to minimize the expected number of machines needed throughout a schedule subject to the following waiting-time constraints. At time 0, a timer with (random) initial value W is started; after time W all jobs must either be finished or running on a machine. The value of W is not known in advance, but its distribution is made available to the scheduler.

In general, if job running times are random, there might be situations in which, after running jobs on a given number of machines, it would be desirable to activate new machines, because the remaining times of unfinished jobs are stochastically too large compared to the time remaining on the timer. A principal result of this paper is that randomness of job running times is essential to such situations; if running times are deterministic, then irrespective of the distribution of W, an optimal policy initially assigns jobs to some number of machines kn (which depends on the distribution of W), and maintains that number while there are jobs available, until the timer has expired, at which point any remaining, as yet unscheduled jobs are assigned to new, unused machines.

This paper also analyzes the dependence of kn and the minimal expected cost on the parameters of the timer distribution when W is either exponentially distributed or uniformly distributed on a finite interval. The determination of kn turns out to have an intriguing number-theoretic flavor.
Approximations and Metric Regularity in Mathematical Programming in Banach Space
Authors: Jourani A. , Thibault L.
Published: October 2008

This paper establishes verifiable conditions ensuring the important notion of metric regularity for general nondifferentiable programming problems in Banach spaces. These conditions are used to obtain Lagrange-Kuhn-Tucker multipliers for minimization problems with infinitely many inequality and equality constraints.
Shortest Integer Vectors
Authors: Scarf Herbert E. , Shallcross David F.
Published: October 2008

Let A be a fixed integer matrix of size m by n and consider all b for which the body Kb = {x: Ax ≤ b} is full dimensional. We examine the set of shortest nonzero integral vectors with respect to the family of norms whose unit balls are given by (Kb − Kb). We show that the number of such shortest vectors is polynomial in the bit size of A, for fixed n. We also show the existence, for any n, of a family of matrices M for which the number of shortest vectors has as a lower bound a polynomial in the bit size of M of the same degree as the polynomial bound.
Filtered Monte Carlo
Authors: Glasserman Paul
Published: October 2008

By a filtered Monte Carlo estimator we mean one whose constituent parts—summands or integral increments—are conditioned on an increasing family of σ-fields. Unbiased estimators of this type are suggested by compensator identities. Replacing a point-process integrator with its intensity gives rise to one class of examples; exploiting Levy's formula gives rise to another.

We establish variance inequalities complementing compensator identities. Among estimators that are (Stieltjes) stochastic integrals, we show that filtering reduces variance if the integrand and the increments of the integrator have conditional positive correlation. We also provide more primitive hypotheses that ensure this condition, making use of stochastic monotonicity properties. Our most detailed conditions apply in a Markov setting where monotone, up-down, and convex generators play a central role. We give examples. As an application of our results, we compare certain estimators that do and do not exploit the property that Poisson arrivals see time averages.
Generalized Quasi-Variational-Like Inequality Problem
Authors: Tian Guoqiang
Published: October 2008

This paper gives some very general results on the generalized quasi-variational-like inequality problem. Since the problem includes all the existing extensions of the classical variational inequality problem as special cases, our existence theorems extend the previous results in the literature by relaxing both continuity and concavity of the functional. The approach adopted in this paper is based on continuous selection-type arguments and thus is quite different from the Berge Maximum Theorem or Hahn-Banach Theorem approach used in the literature.
Tandem Queues with Correlated Service Times and Finite Capacity
Authors: Ziediņš Ilze
Published: October 2008

This paper studies tandem queues where the ith customer has the same service time, Xi, at each queue and capacity at each queue is finite. The behaviour of the tandem queue is examined in the presence and absence of blocking. For bounded service time distributions, it is already known that provided there is sufficient capacity available to prevent blocking, it is optimal to allocate the capacity uniformly. We show that for some simple service time distributions with support on two points, the throughput can be calculated exactly and that it is always optimal to allocate the capacity as uniformly as possible, even when blocking occurs. These results contrast with those of previous authors that suggest that a ‘reversed-bowl’ allocation of capacity may be optimal when service times are independent from queue to queue.
Bounds on the Performance of Dynamic Routing Schemes for Highly Connected Networks
Authors: Kelly F. P.
Published: October 2008

We describe a procedure for bounding the performance of dynamic routing schemes for loss or queueing networks. The bound is developed from a network flow synthesis of a collection of Markov decision processes, one for each resource of the network. The bound emerges as a solution to a dual pair of convex programming problems, where the primal problem describes mean flows through the network and the dual problem describes implied costs and surplus values at resources of the network. The bound is particularly appropriate for large highly connected networks, where it may be approached by simple trunk reservation or threshold routing schemes.
Bounding a Probability Measure Over a Polymatroid with an Application to Transportation Problems
Authors: Ball Michael O. , Shanthikumar J. George
Published: October 2008

For M = {1, …, m} and a supermodular set function f: 2M → ℛ, define the polymatroid P(M, f) = {x: ∑j∈A xj ≥ f(A), A ⊆ M; x ∈ ℛm}. We develop a bound for the probability P{X ∈ P(M, f)}, where X is a random m-vector. In particular we show that if X, X1, …, Xm, are independent and identically distributed nonnegative random variables with new better than used (NBU) distribution function, then P{X ∈ P(M, f)} ≥ P{X ≥ f(M̂)}, where M̂ = arg max {f(A): A ⊆ M}. We apply this result to transportation problems with random supply and/or demand. Suppose we have a set K = {1, …, k} of k supply nodes with a random supply Si, i ∈ K and a set N = {1, …, n} of n demand nodes with a random demand Dj, j ∈ N. Let β be the probability that the random demand can be met by the random supply. If the demand and supply are mutually independent, D1, …, Dn, are independent, and S1, …, Sk, are independent and have NBU distribution function, then β ≤ ∏j=1n P{Zj ≥ Dj}, where Zj = ∑i∈K Si rij, j∈N and rij takes the value one if node i can supply the demand node j and zero otherwise (i ∈ K and j ∈ N).
On Quadratic Cost Criteria for Option Hedging
Authors: Schäl Manfred
Published: October 2008

Consider an option with maturity time T corresponding to a contingent claim H (in an incomplete market). A fair hedging price for H should take into account an optimal dynamical hedging plan against H. Let Ct be the cumulative cost and ℑt be the set of events of the history up to time t. You can choose the plan at time t such that you minimize

(i) E[{Ct+1 − Ct}2 ∣ ℑt],

(ii) E[{CT − Ct}2 ∣ ℑt], or

(iii) E[{CT − C0}2].

Sufficient conditions on the underlying stochastic process (in discrete time) are provided such that the fair hedging price does not depend on the choice of (i), (ii), or (iii), which fact should increase its acceptability.
Markov Decision Models with Weighted Discounted Criteria
Authors: Feinberg Eugene A. , Shwartz Adam
Published: October 2008

We consider a discrete time Markov Decision Process with infinite horizon. The criterion to be maximized is the sum of a number of standard discounted rewards, each with a different discount factor. Situations in which such criteria arise include modeling investments, production, modeling projects of different durations and systems with multiple criteria, and some axiomatic formulations of multi-attribute preference theory. We show that for this criterion for some positive ε there need not exist an ε-optimal (randomized) stationary strategy, even when the state and action sets are finite. However, ε-optimal Markov (nonrandomized) strategies and optimal Markov strategies exist under weak conditions. We exhibit ε-optimal Markov strategies which are stationary from some time onward. When both state and action spaces are finite, there exists an optimal Markov strategy with this property. We provide an explicit algorithm for the computation of such strategies and give a description of the set of optimal strategies.