bluuebunny/crossref_metadata_2025 huggingface dataset:
On a Class of Totally Unimodular Matrices
Authors: Yannakakis Mihalis
Published: October 2008

We examine the class of totally unimodular matrices-that contain no odd cycles, which we call restricted totally unimodular (RTUM). We show that a matrix is RTUM if and only if it can be decomposed in a very simple way into the incidence matrices (or their transposes) of bipartite graphs or directed graphs, and give a linear time algorithm to perform this task. Based on this decomposition, we show that the 0,1 Integer Programming Problem with an RTUM matrix of constraints has the same time complexity as the b-matching and the max flow problems.
Facets of the Bipartite Subgraph Polytope
Authors: Barahona Francisco , Grötschel Martin , Mahjoub Ali Ridha
Published: October 2008

The bipartite subgraph polytope PB(G) of a graph G = [V, E] is the convex hull of the incidence vectors of all edge sets of bipartite subgraphs of G. We show that all complete subgraphs of G of odd order and all so-called odd bicycle wheels contained in G induce facets of PB(G). Moreover, we describe several methods with which new facet defining inequalities of PB(G) can be constructed from known ones. Examples of these methods are contraction of node sets in odd complete subgraphs, odd subdivision of edges, certain splittings of nodes, and subdivision of all edges of a cut. Using these methods we can construct facet defining inequalities of PB(G) having coefficients of order |V|2.
The Principle of Optimality in Dynamic Programming with Returns in Partially Ordered Sets
Authors: Henig Mordechai I.
Published: October 2008

A general sequential model is defined where returns are in a partially ordered set. A distinction is made between maximal (nondominated) returns and greatest returns. We show that Bellman's principle of optimality is valid with respect to maximal returns and it leads to an algorithm to approximate these returns. We argue that significantly greater effort is needed to apply this algorithm to maximal returns than to greatest returns.
A Conical Algorithm for Globally Minimizing a Concave Function Over a Closed Convex Set
Authors: Tuy H. , Thieu T. V. , Thai Ng. Q.
Published: October 2008

In this paper we are concerned with the problem of finding the global minimum of a concave function over a closed, convex, possibly unbounded set in Rn. The intrinsic difficulty of this problem is due to the fact that a local minimum of the objective function may fail to be a global one—which makes the conventional methods of local optimization almost useless.
Cores of Convex Games Without Side Payments
Authors: Greenberg Joseph
Published: October 2008

This paper gives a short and direct proof that a convex game without side payments has a nonempty core. One setting in which such games arise is that of social choice, where the notion of equilibrium is in fact the core of the induced game.
Bounds and Heuristics for Capacitated Routing Problems
Authors: Haimovich M. , Rinnooy Kan A. H. G.
Published: October 2008

In a capacitated routing problem, the objective is to minimize the total distance travelled by vehicles of limited capacity to serve a set of customers that are located in the Euclidean plane. We develop asymptotically optimal bounds and heuristics for this problem, under the assumption that the capacity of a vehicle is expressed in terms of an upper bound on the number of customers that it can serve. The analysis culminates in an algorithm that, for a given capacity and given ϵ, will find a solution with relative error at most ϵ in time polynomial in the number of customers.
Sequencing Problems in Two-Server Systems
Authors: Calderbank A. R. , Coffman E. G. , Flatto L.
Published: October 2008

We analyze a service system in which two identical servers move one at a time along a linear array of N positions. Requests for service, each designating one of the N positions, join a first-in-first-out queue, where processing of the nth request does not begin until processing of the (n − 1)th requested is completed. Processing the nth request entails determining which server to move, moving this server to the requested position, and then performing the service. Several potential applications of the model are mentioned, the most notable being the design of computer storage systems with multiple access devices.

Within a simple probability model we compare server-selection policies in terms of the equilibrium expected distance a server is moved in processing a request. Distance is measured under two regimes, both assigning a unit distance between adjacent positions. In the first, the positions are thought of as equally spaced along a line (interval), and in the second, equally spaced along a circle (positions 1 and N are adjacent).

For the interval problem the server-selection policies examined include the partition rule, whereby die interval is bisected and a server restricted to the requests in each half-interval, and the nearer-server rule whereby service is always provided by the server closer to the requested position, with ties broken in favor of the right-hand server. Under the assumption that requested positions are distributed uniformly over the set of N, our results show that expected server motion under the nearer-server rule is approximately 0.1625 N for moderately large N, which is to be compared with the known result of N/6 = 0.1666 … N for the partition rule. We also derive an optimization rule for which numerical calculations indicate that 0.1598 N is the approximate performance for large N. A number of other results plus two conjectures are presented which characterize optimization rules on the interval. Finally, extensive numerical calculations are displayed which describe the joint distributions of server positions under the nearer-server and a related rule.

For the more tractable circle problem we prove that die nearer-server rule is optimal, and we derive an explicit form for the stationary density of the distance between servers. It is noted that the nearer-server rule is also optimal when the circle is generalized to 2-point homogeneous spaces (e.g., a Euclidean sphere) in more than one dimension.
A Note on Differentiability of Global Optimal Values
Authors: Fujiwara Okitsugu
Published: October 2008

The differentiability of global optimal values for smooth constrained programs with respect to general perturbations is considered. The strong Whitney C2-topology is used to the space of objective functions and constraints. It will be shown generically the global optimal value is twice continuously differentiable with respect to the function space of objective functions and constraints. An application of this genericity argument to a nonsmooth objective function—a function of maximum type—is also discussed.
Distributional Strategies for Games with Incomplete Information
Authors: Milgrom Paul R. , Weber Robert J.
Published: October 2008

We study games with incomplete information from a point of view which emphasizes the empirical predictions arising from game-theoretic models. Using the notion of “distributional” strategies, we prove four main theorems: (i) a mixed-strategy Nash equilibrium existence theorem, (ii) a pure-strategy equilibrium existence theorem, (iii) a pure-strategy ϵ-equilibrium existence theorem, and (iv) a theorem describing how the set of equilibria of a game varies with the parameters of the game.
Von Neumann-Morgenstern Utilities and Cardinal Preferences
Authors: Chichilnisky Graciela
Published: October 2008

We study the aggregation of preferences when intensities are taken into account: the aggregation of cardinal preferences, and also of von Neumann-Morgenstern utilities for choices under uncertainty. We show that with a finite number of choices there exist no continuous anonymous aggregation rules that respect unanimity, for such preferences or utilities. With infinitely many (discrete sets of) choices, such rules do exist and they are constructed here. However, their existence is not robust: each is a limit of rules that do not respect unanimity. Both results are for a finite number of individuals.

The results are obtained by studying the global topological structure of spaces of cardinal preferences and of von Neumann-Morgenstern utilities. With a finite number of choices, these spaces are proven to be noncontractible. With infinitely many choices, on the other hand, they are proven to be contractible.
Continuity of Generalized Gradients and Multipliers Under Perturbations
Authors: Zolezzi Tullio
Published: October 2008

We prove that the multiplier rule, given by Clarke for mathematical programming problems with locally Lipschitz data, is stable under epi-convergent data perturbations in the finite-dimensional case for global solutions. This stability result is derived from a continuity theorem for generalized gradients extending the classical formula lim ∇fn = ∇(lim fn).

Continuous dependence theorems for multipliers in the Fritz-John form proved in this paper extend stability results of Gauvin, Robinson and others for nonlinear programming problems with smooth data.
A Note on Finding Minimum-Cost Edge-Disjoint Spanning Trees
Authors: Roskind James , Tarjan Robert E.
Published: October 2008

Let G be an undirected graph with n vertices and m edges, such that each edge has a real-valued cost. We consider the problem of finding a set of k edge-disjoint spanning trees in G of minimum total edge cost. This problem can be solved in polynomial time by the matroid greedy algorithm. We present an implementation of this algorithm that runs in O(m log m + k2n2) time. If all edge costs are the same, the algorithm runs in O(k2n2) time. The algorithm can also be extended to find the largest k such that k edge-disjoint spanning trees exist in O(m2) time. We mention several applications of the algorithm.
Multivariate New Better than Used Distributions
Authors: Marshall Albert W. , Shaked Moshe
Published: October 2008

A general theory of multivariate new better than used (NBU) distributions is developed. Using the general theory some multivariate NBU conditions are introduced and studied. Some of the results apply as well to multivariate increasing hazard rate average (IHRA) and exponential distributions. Proofs of some related well-known implications are simplified.
On the Duality Gap in Nonconvex Optimization
Authors: Pappalardo M.
Published: October 2008

Given a nonconvex constrained minimization problem, we introduce the dual problem by means of the ordinary Lagrangean function. The aim of the paper is to give, by means of the “image problem,” an estimate of the duality gap using the definition of lack of convexity of a function.
An Application of the Theory of Weak Convergence to the Dynamic Perishable Inventory Problem with Discrete Demand
Authors: Nahmias Steven , Schmidt Charles P.
Published: October 2008

This paper develops a technique for analyzing dynamic inventory problems with discrete demand using the theory of weak convergence. We treat the dynamic fixed life perishable inventory problem with discrete demand. The optimal structure has been established assuming continuous demand. We construct an infinite sequence of continuous demand distributions that converge weakly to a discrete distribution, and show that the key results carry over in the limit.
Nonsmooth Milyutin-Dubovitskii Theory and Clarke's Tangent Cone
Authors: Watkins G. G.
Published: October 2008

In optimization theory the idea of approximating nonconvex sets by convex cones which satisfy an abstract condition—the Intersection Principle—is due to Milyutin and Dubovitskii. This approach has been successfully applied to optimization problems with differentiable data. The validity of the Intersection Principle for the Clarke tangent cone, which is the apposite approximant for nonsmooth constraints, is established via an intersection theorem which relates the Clarke tangent cone of an intersection of sets to the intersection of the individual Clarke tangent cones, provided the latter are inseparable. This allows an extension of the Milyutin-Dubovitskii approach to nonsmooth optimization theory. A multiplier rule, of the type obtained by Clarke and Hiriart-Urruty, for a nonsmooth inequality constrained problem, is thereby encompassed within Milyutin-Dubovitskii theory.
Transversality Conditions for Some Infinite Horizon Discrete Time Optimization Problems
Authors: Ekeland Ivar , Scheinkman José Alexandre
Published: October 2008

This paper considers a class of discrete-time, infinite-horizon optimization problems arising in economics. Necessary optimality conditions for such problems consist of an Euler equation and a transversality condition at infinity. Our concern here is with the latter condition.

Previous results for this type of problem have required such restrictions as concavity and boundedness of the utility functions whose sum is being maximized. Here we derive a transversality condition that remains valid under considerably more general hypotheses. In doing so, we introduce methods that may also be applicable to other situations, such as optimization in continuous time.
A Sequential Stochastic Assignment Problem in a Partially Observable Markov Chain
Authors: Nakai Toru
Published: October 2008

A sequential stochastic assignment problem in a stationary Markov chain, where the states are not known explicitly, is considered. This is an optimization problem in a partially observable Markov chain, and an optimal policy and the total expected reward under this policy are obtained. Here we specify the learning procedure by the Bayes' theorem, and the optimal policy is not always a critical number policy. As a special case of this problem, a problem of optimal selections is considered, and a relation to former results of a sequential stochastic assignment problem is observed.
Markov Decision Processes with a Borel Measurable Cost Function—The Average Case
Authors: Kurano Masami
Published: October 2008

We consider a Markov decision process with a Borel measurable cost function. We introduce a p-step contraction property for the average cost case. By use of this method, the validity of the optimality equation and the existence of ϵ-optimal stationary policies are proved. As some applications, the sequential replacement model and the inventory model are considered.
On Minimizing the Expected Makespan and Flow Time in Stochastic Flow Shops with Blocking
Authors: Wie Sung-Hwan , Pinedo Michael
Published: October 2008

Consider an m machine flow shop with no intermediate storage between any two successive machines and blocking. The processing time of job j, j = 1, …, n, on each one of the m machines is equal to the random variable Xj and is distributed according to Fj. We assume that the processing times are stochastically ordered in such a way that F1 ≤st ⋯ ≤st Fn. We show that the sequence 1, 3, 5, …, n − 1, n, n − 2, …, 6, 4, 2 when n is even and the sequence 1, 3, 5, …, n − 2, n, n − 1, …, 6, 4, 2 when n is odd minimizes the expected makespan and that the sequence 1, …, n minimizes the expected flow time.
A Stochastic Calculus Model of Continuous Trading: Optimal Portfolios
Authors: Pliska Stanley R.
Published: October 2008

The problem of choosing a portfolio of securities so as to maximize the expected utility of wealth at a terminal planning horizon is solved via stochastic calculus and convex analysis. This problem is decomposed into two subproblems. With security prices modeled as semimartingales and trading strategies modeled as predictable processes, the set of terminal wealths is identified as a subspace in a space of integrable random variables. The first subproblem is to find the terminal wealth that maximizes expected utility. Convex analysis is used to derive necessary and sufficient conditions for optimality and an existence result. The second subproblem of finding the admissible trading strategy that generates the optimal terminal wealth is a martingale representation problem. The primary advantage of this approach is that explicit formulas can readily be derived for the optimal terminal wealth and the corresponding expected utility, as is shown for the case of an exponential utility function and a risky security modeled as geometric Brownian motion.
Rolling Planning Horizons: Error Bounds for the Dynamic Lot Size Model
Authors: Lee Chung-Yee , Denardo Eric V.
Published: October 2008

A new and tight bound is placed on the error induced by imposing a finite time horizon T on the dynamic lot size model. This bound equals the value of perfect information about the data beyond the time horizon T. With this bound, one can assess the value of using the dynamic lot size model repeatedly on a rolling basis with a time horizon of T periods. When this bound is low the time horizon is long enough. When this bound is not low, it may pay to invest in forecasts of demands for later periods, thereby increasing the time horizon.
Generalized S-Shapedness of Reliability Functions
Authors: Pilpel Shaiy
Published: October 2008

Reliability functions have the property that if they intersect the diagonal y = x it is done in an S-shaped form (Moore and Shannon).

In this paper a wider class of polynomials is presented, the members of which form a dense grid on the unit square. The S-shapedness intersection property holds whenever a reliability function intersects a polynomial in this set.

The members of this set are all reliability polynomials. The diagonal y = x is also a member of this set, thus a generalization of Moore-Shannon result is achieved.
Upper Bounds for Single Server Queues with Doubly Stochastic Poisson Arrivals
Authors: Rolski Tomasz
Published: October 2008

Consider the following type of single server queues. Arrivals are according to a Doubly Stochastic Poisson process with a stationary, ergodic random intensity {λ(t)}. Service times are independent, identically distributed, also independent from arrivals. It is proven that the mean stationary work-load is not greater than E[ω(λ(0))], where ω(a) denotes the mean stationary work-load in the M/GI/1 queue with arrival intensity a and the same service process. Similar results are given for the mean stationary queue size and the mean stationary delay.
The Uniqueness of Stationary Distributions for the GI/G/S Queue
Authors: Wolfson Barry
Published: October 2008

Kiefer and Wolfowitz (Kiefer, J., J. Wolfowitz. 1955. On the theory of queues with many servers. Amer. Math. Soc. 78 1–18.) showed that there exists a unique proper stationary limiting distribution for the stochastic process representing the workload at arrival epochs in a multiple-server queue when the utilization per server is less than one. An alternate proof of the uniqueness is presented here which avoids using approximating discrete-state Markov chains.
A Family of Simplex Variants Solving an m × d Linear Program in Expected Number of Pivot Steps Depending on d Only
Authors: Adler Ilan , Karp Richard , Shamir Ron
Published: October 2008

We present a family of variants of the Simplex method, which are based on a Constraint-By-Constraint procedure: the solution to a linear program is obtained by solving a sequence of subproblems with an increasing number of constraints. We discuss several probabilistic models for generating linear programs. In all of them the underlying distribution is assumed to be invariant under changing the signs of rows or columns in the problem data. A weak regularity condition is also assumed. Under these models, for linear programs with d variables and m + d inequality constraints, the expected number of pivots required by these algorithms is bounded by a function of min(m, d) only. In particular this means that, for a fixed number of variables, the expected number of pivots is bounded by a constant when the number of constraints tends to infinity. Since Smale's original model [Smale, S. 1983. On the average speed of the simplex method of linear programming. Math. Programming 27.] satisfies our probabilistic assumptions, the same results apply to his model, although not to the particular algorithm he analyzes. We also present some results for models generating only feasible linear programs, and for Bland's pivoting rule. We conclude with a discussion of our probabilistic models, and show why they are inadequate for obtaining meaningful results unless d and m are of the same order of magnitude.
Optimal Sequential Assignment
Authors: Kennedy D. P.
Published: October 2008

For each job n (=1, …, N) there is an associated random variable Xn and for each person m (=1, …, N) there is an associated constant pm so that if job n is assigned to person m a reward pmXn is obtained. We do not assume that the Xn are necessarily independent. The jobs are observed sequentially and must be assigned nonanticipatively to the persons so as to maximise the total expected reward. The optimal assignment is established for both the case when N is finite and when N is infinite.
A Gauss-Newton Approach to Solving Generalized Inequalities
Authors: Burke Jim , Han S.-P.
Published: October 2008

Generalized inequalities are systems of the form g(x) ≤K 0, where g maps between normed linear spaces and “≤K” denotes the partial order induced by the closed convex cone K (e.g., K = R+m1 × {0}Rm2). In this paper a Gauss-Newton type algorithm is presented for minimizing the distance function [Formula: see text] The technique globalizes the well-known Newton methods for solving generalized inequalities, and overcomes the difficulties associated with subgradient methods for the global minimization of ρ.
On Iterated Minimization in Nonconvex Optimization
Authors: Jongen H. Th. , Möbert T. , Tammer K.
Published: October 2008

In dynamic programming and decomposition methods one often applies an iterated minimization procedure. The problem variables are partitioned into several blocks, say x and y. Treating y as a parameter, the first phase consists of minimization with respect to the variable x. In a second phase the minimization of the resulting optimal value function depending on y is considered. In this paper we treat this basic idea on a local level. It turns out that strong stability (in the sense of Kojima) in the first phase is a natural assumption. In order to show that the iterated local minima of the parametric problem lead to a local minimum for the whole problem, we use a generalized version of a positive definiteness criterion of Fujiwara-Han-Mangasarian.
A 98%-Effective Lot-Sizing Rule for a Multi-Product, Multi-Stage Production / Inventory System
Authors: Roundy Robin
Published: October 2008

We study a multi-product, multi-stage production inventory system in continuous time. In-process and finished goods are referred to as products and inventories of a single item held at different locations are treated as different products. External demand can occur for any or all of the products at a constant, product-dependent rate.

When an order is placed for a product it is instantly delivered. The set-up cost is a function of the set of products being ordered at that point in time. The goal is to schedule orders for each of the products over an infinite horizon so as to minimize the long-run average cost.

We define a new class of policies in which each product uses a stationary interval of time between successive orders, and the ratio of the order intervals of any two products is an integer power of two. We show that there is always a policy in this class that is within 2% of optimal. This extends a similar result for the one-warehouse, multi-retailer system. For assembly systems we show how to compute such a policy in 0(N log N) time. For general systems a sequence of max-flow, min-cut computations is required. The algorithm is efficient for very large systems.
On the Efficiency of Newton's Method in Approximating All Zeros of a System of Complex Polynomials
Authors: Renegar J.
Published: October 2008

This paper studies the efficiency of an algorithm based on Newton's method is approximating all zeros of a system of polynomials f = (f1, f2, …, fn): ℂn → ℂn. The criteria for a successful approximation y of a zero w of f include the following: given ϵ > 0, y is within distance ϵ of w; Newton's method applied to f and initiated at y results in quadratic convergence to w; given ϵ > 0, |fi(y)| < ϵ for all i = 1, 2, …, n, where | | is the Euclidean norm on ℂ. It is shown that, probabilistically, each zero of f is successfully approximated within a determined number of steps.
Hermite Normal Form Computation Using Modulo Determinant Arithmetic
Authors: Domich P. D. , Kannan R. , Trotter L. E.
Published: October 2008

This paper describes a new class of Hermite normal form solution procedures which perform modulo determinant arithmetic throughout the computation. This class of procedures is shown to possess a polynomial time complexity bound which is a function of the length of the input string. Computational results are also given.
Sensitivity Analysis for Stochastic Scheduling Problems
Authors: Glazebrook K. D.
Published: October 2008

We seek to evaluate the effect which departures from assumed parameter values have upon the performance of scheduling strategies. Most of the material is presented in terms of a single machine scheduling model, denoted {(Rj, ρj, α), 1 ≤ j ≤ N}. The theoretical basis of the sensitivity analysis is developed from previous work by the author and Gittins.
Penalty Functions and Duality in Stochastic Programming Via ϕ-Divergence Functionals
Authors: Ben-Tal A. , Teboulle M.
Published: October 2008

The paper considers stochastically constrained nonlinear programming problems. A penalty function is constructed in terms of a “distance” between random variables, defined in terms of the ϕ-divergence functional (a generalization of the relative entropy). A duality theory is developed in which a general relation between ϕ-divergence and utility functions is revealed, via the conjugate transform, and a new type of certainty equivalent concept emerges.
The Asymptotic Optimality of the LPT Rule
Authors: Frenk J. B. G. , Rinnooy Kan A. H. G.
Published: October 2008

For the problem of minimizing makespan on parallel machines of different speed, the behaviour of list scheduling rules is subjected to a probabilistic analysis under the assumption that the processing requirements of the jobs are independent, identically distributed nonnegative random variables. Under mild conditions on the probability distribution, we obtain strong asymptotic optimality results for the LPT (Longest Processing Time) rule, in which the jobs are assigned to the machines in order of nonincreasing processing requirements.
The Multi-Armed Bandit Problem: Decomposition and Computation
Authors: Katehakis Michael N. , Veinott Arthur F.
Published: October 2008

This paper is dedicated to our friend and mentor, Cyrus Derman, on the occasion of his 60th birthday.

The multi-armed bandit problem arises in sequentially allocating effort to one of N projects and sequentially assigning patients to one of N treatments in clinical trials. Gittins and Jones (Gittins, J. C., Jones, D. M. 1974. A dynamic allocation index for the sequential design of experiments. J. Gani, K. Sarkadi, L. Vince, eds. Progress in Statistics. European Meeting of Statisticians, 1972, 1, North Holland, Amsterdam, 241–266.) have shown that one optimal policy for the N-project problem, an N-dimensional discounted Markov decision chain, is determined by the following largest-index rule. There is an index for each state of each given project that depends only on the data of that project. In each period one allocates effort to a project with largest current index. The purpose of this paper is to give a short proof of this result and a new characterization of the index of a project in state i, viz., as the maximum expected present value in state i for the restart-in-i problem in which, in each state and period, one either continues allocating effort to the project or immediately restarts the project in state i. Moreover, it is shown that an approximate largest-index rule yields an approximately optimal policy. These results lead to more efficient methods of computing the indices on-line and/or for sparse transition matrices in large state spaces than have been suggested heretofore. By using a suitable implementation of successive approximations, a policy whose expected present value is within 100ϵ% of the maximum possible range of values of the indices can be found on-line with at most (N + T − 1)TM operations where M is the number of operations required to calculate one approximation, T is the least integer majorizing the ratio ln ϵ/ln a and 0 < a < 1 is the discount factor.
A Nonzero-Sum Extension of Dynkin's Stopping Problem
Authors: Ohtsubo Yoshio
Published: October 2008

We consider two-person nonzero-sum stopping games for random sequences. The problem is divided into two cases with regard to underlying sequences. In the first case with infinite horizon and in the second one with finite stages we find equilibrium points and show that the corresponding equilibrium values satisfy certain value-relations. The values are constructed by the backward inductions. Also in both cases with infinite horizon we give sufficient conditions for a pair of stopping times to be an equilibrium point in terms of value-relation. Finally independent and Markov models are dealt with and especially in the latter the existence theorem for equilibrium points of the second case is given under suitable conditions.
Minimizing a Quadratic Payoff with Monotone Controls
Authors: Barron Emmanuel Nicholas , Jensen Robert , Malliaris A. G.
Published: October 2008

Many important problems in economic dynamics can be formulated as optimal control problems in which the controls must be monotone functions of time. In this paper we will completely solve a problem with quadratic payoff involving the control and the derivative of the control by constructing optimal monotone controls. Several generalizations and examples are also given.
Stochastic Orderings for Markov Processes on Partially Ordered Spaces
Authors: Massey William A.
Published: October 2008

The purpose of this paper is to develop a unified theory of stochastic ordering for Markov processes on countable partially ordered state spaces. When such a space is not totally ordered, it can induce a wide range of stochastic orderings, none of which are equivalent to sample path comparisons. Similar comparison theorems are also developed for non-Markov processes that are functions of Markov processes and for time-inhomogeneous Markov processes. Such alternative orderings can be quite useful when analyzing multi-dimensional stochastic models such as queueing networks.
Application of Degree Theory in Stability of the Complementarity Problem
Authors: Ha Cu Duong
Published: October 2008

In this paper we study the behavior of a solution of the complementarity problem when the problem is perturbed. The basic result is that if the degree of a certain function is nonzero then the problem is stable. We show that several well-known conditions for the existence of a solution to the problem also imply stability of the problem. We also show that in the nondegenerate case there are simple conditions that ensure stability.
The Complexity of Markov Decision Processes
Authors: Papadimitriou Christos H. , Tsitsiklis John N.
Published: October 2008

We investigate the complexity of the classical problem of optimal policy computation in Markov decision processes. All three variants of the problem (finite horizon, infinite horizon discounted, and infinite horizon average cost) were known to be solvable in polynomial time by dynamic programming (finite horizon problems), linear programming, or successive approximation techniques (infinite horizon). We show that they are complete for P, and therefore most likely cannot be solved by highly parallel algorithms. We also show that, in contrast, the deterministic cases of all three problems can be solved very fast in parallel. The version with partially observed states is shown to be PSPACE-complete, and thus even less likely to be solved in polynomial time than the NP-complete problems; in fact, we show that, most likely, it is not possible to have an efficient on-line implementation (involving polynomial time on-line computations and memory) of an optimal policy, even if an arbitrary amount of precomputation is allowed. Finally, the variant of the problem in which there are no observations is shown to be NP-complete.
Generalizations of Cliques, Odd Cycles and Anticycles and Their Relation to Independence System Polyhedra
Authors: Euler R. , Jünger M. , Reinelt G.
Published: October 2008

Padberg (Padberg, M. W. 1973. On the facial structure of set packing polyhedra. Math. Programming 5 199–215.) has shown that if a graph G with vertex set V constitutes a clique (odd cycle, odd anticycle), then the inequality Σx∈Vxv ≤ 1 (Σx∈Vxv ≤ ½(|V| − 1), Σx∈Vxv ≤ 2) defines a facet of P(ℐST(G)), the convex hull of the incidence vectors of stable sets in G. We generalize the concepts of cliques, odd cycles and anticycles to arbitrary independence systems (E, ℐ) and show that the corresponding inequalities define facets of P(ℐ), the convex hull of the incidence vectors of independent sets.
A Posteriori Error Bounds for the Linearly-Constrained Variational Inequality Problem
Authors: Pang Jong-Shi
Published: October 2008

In this paper, we derive a posteriori error bound of an approximate solution to a linearly-constrained variational inequality problem. Three measures of error are used, with each depending on a particular characterization of an exact solution and related to a certain class of iterative methods.
A Continuous Deformation Algorithm on the Product Space of Unit Simplices
Authors: Doup T. M. , Talman A. J. J.
Published: October 2008

A continuous deformation algorithm is introduced on S × [1, ∞), where S denotes the product space of unit simplices, with arbitrary grid refinement between two subsequent levels. The set S × [1, ∞) is triangulated in such a way that for each m, m = 1, 2, …, S × {m} is triangulated by the so-called V-triangulation. The algorithm starts by applying a variable dimension algorithm on S until an approximating simplex has been found on level 1. Then the algorithm follows a path of approximating simplices in S × [1, ∞), starting on level 1, until a certain level or a certain accuracy of a solution of the underlying problem has been reached. If the algorithm returns to level 1, then we again apply the variable dimension algorithm until a new approximating simplex is found on level 1, etc. We allow solutions to lie on the boundary of S × [1, ∞) in which case the algorithm, in general, will follow a path on the boundary of S × [1, ∞).
Relaxation Methods for Linear Programs
Authors: Tseng Paul , Bertsekas Dimitri P.
Published: October 2008

In this paper we propose a new method for solving linear programs. This method may be viewed as a generalized coordinate descent method whereby the descent directions are chosen from a finite set. The generation of the descent directions are based on results from monotropic programming theory. The method may be alternatively viewed as an extension of the relaxation method for network flow problems (Bertsekas, D. P. 1982. A unified framework for minimum cost network flow problems. LIDS Report P-1245-A, Mass. Institute of Technology, October; also 1985. Math. Programming 32 125–145; Bertsekas, D. P., Tseng, P. 1985. Relaxation methods for minimum cost ordinary and generalized network flow problems. LIDS Report P-1462, Massachusetts Institute of Technology, May.). Node labeling, cuts, and flow augmentation paths in the network case correspond to, respectively, tableau pivoting, rows of tableaus, and columns of tableaus possessing special sign patterns in the linear programming case.
Second Order Directional Derivatives in Parametric Optimization Problems
Authors: Seeger Alberto
Published: October 2008

We characterize the second order directional derivative in the sense of Ben-Tal and Zowe of a marginal function Ψ of the following general form: Ψ(x) − Inf{f(x, y) ∣ y ∈ Ω(x)}. This requires us to introduce some geometrical notions as, for example, the first and second order tangent directions to a multifunction. The main results are then applied to some particular types of marginal functions.
Communication Equilibria in Repeated Games with Incomplete Information
Authors: Forges Françoise
Published: October 2008

Correlated equilibria (in the sense of Aumann, i.e., normal form correlated equilibria) are studied in two-person infinitely repeated games with lack of information on one side. Extensions of the solution concept are introduced, several of which are shown to be payoff equivalent in the model under consideration.

A normal form correlated equilibrium is a Nash equilibrium of the game where each player gets a private output from a correlation device before the beginning of the original game. An r-device (r = 0, 1, …, ∞) is a communication device, receiving an input from each player before every stage t = 1, …, r and selecting a pair of outputs, one for each player, at every stage t = 1, 2, …, according to a memory dependent transition probability. An r-communication equilibrium is a Nash equilibrium of the game extended by means of an r-device. Let C (resp. Dr, r = 0, 1, …, ∞) be the set of normal form correlated (resp. r-communication) equilibrium payoffs. D0 is the set of “extensive form correlated equilibrium payoffs,” achieved by means of an “autonomous device,” acting only by sending a stream of outputs to each player. And D∞ is the set of all communication equilibrium payoffs, corresponding to communication devices which can receive inputs at every stage (even arbitrarily large). The paper characterizes the different sets and investigate whether they coincide.
Positive Dependence, Upper Sets, and Multidimensional Partitions
Authors: Sampson Allan R. , Whitaker Lyn R.
Published: October 2008

Let U be an upper set contained in the finite discrete lattice L = {1, …, D(1)} × ⋯ × {1, …, D(p)}. Representations for U are obtained and shown to correspond to certain multidimensional partitions of integers. It is shown that for p = 3, the number of possible upper sets in L is [Formula: see text]. Various other representation and enumeration results are obtained for related settings. Considered are a variety of applications to multivariate positive dependence and various notions in statistics and reliability theory.
Generalized Equilibrium Results for Games with Incomplete Information
Authors: Balder Erik J.
Published: October 2008

Milgrom and Weber (Milgrom, P. R., Weber, R. J. 1985. Distributional strategies for games with incomplete information. Math. Oper. Res. 10 619–632.) gave an existence result for a Nash equilibrium in a game with incomplete information, using their notion of a distributional strategy. Here we obtain a substantial improvement of their existence result in terms of the more traditional concept of a behavioral strategy. This improvement is reached very naturally as an application of a theory of weak convergence for transition probabilities, which is recapitulated extensively in this paper. Also, a new result on the weak convergence of product transition probabilities is included.
A Diffusion Model for Optimal Portfolio Selection in the Presence of Brokerage Fees
Authors: Taksar Michael , Klass Michael J. , Assaf David
Published: October 2008

We consider a financial market model with two assets. One has deterministic rate of growth, while the rate of growth of the second asset is governed by a Brownian motion with drift. We can shift money from one asset to another; however, there are losses of money (brokerage fees) involved in shifting money from the risky to the nonrisky asset. We want to maximize the expected rate of growth of funds.

It is proved that an optimal policy keeps the ratio of funds in risky and nonrisky assets within a certain interval with minimal effort.
Cooling Schedules for Optimal Annealing
Authors: Hajek Bruce
Published: October 2008

A Monte Carlo optimization technique called “simulated annealing” is a descent algorithm modified by random ascent moves in order to escape local minima which are not global minima. The level of randomization is determined by a control parameter T, called temperature, which tends to zero according to a deterministic “cooling schedule.” We give a simple necessary and sufficient condition on the cooling schedule for the algorithm state to converge in probability to the set of globally minimum cost states. In the special case that the cooling schedule has parametric form T(t) = c/log(1 + t), the condition for convergence is that c be greater than or equal to the depth, suitably defined, of the deepest local minimum which is not a global minimum state.
One-Processor Scheduling with Symmetric Earliness and Tardiness Penalties
Authors: Garey Michael R. , Tarjan Robert E. , Wilfong Gordon T.
Published: October 2008

We consider one-processor scheduling problems having the following form: Tasks T1, T2, …, TN are given, with each Ti having a specified length li and a preferred starting time ai (or, equivalently, a preferred completion time bi). The tasks are to be scheduled nonpreemptively (i.e., a task cannot be split) on a single processor to begin as close to their preferred starting times as possible. We examine two different cost measures for such schedules, the sum of the absolute discrepancies from the preferred starting times and the maximum such discrepancy. For the first of these, we show that the problem of finding minimum cost schedules is NP-complete; however, we give an efficient algorithm that finds minimum cost schedules whenever the tasks either all have the same length or are required to be executed in a given fixed sequence. For the second cost measure, we give an efficient algorithm that finds minimum cost schedules in general, with no constraints on the ordering or lengths of the tasks.
Sensitivity Analysis in Variational Inequalities
Authors: Dafermos Stella
Published: October 2008

In this paper we derive conditions for the local uniqueness, continuity and differentiability of a solution of parametric variational inequalities. Our approach is new and has a strong geometric flavor. As an illustration we discuss the sensitivity of the classical complementarity problem.
Exhaustive Nondegenerate Conical Processes for Concave Minimization on Convex Polytopes
Authors: Hamami M. , Jacobsen S. E.
Published: October 2008

An exhaustive and nondegenerate cone splitting process is defined and an algorithm stated for minimizing a quasi-concave function on a bounded convex polytope described by a system of linear inequalities. The algorithm crucially splits upon vertices and it is shown that this class of algorithms converges finitely to an optimal solution.
Solution Bases of Multiterminal Cut Problems
Authors: Hassin Refael
Published: October 2008

Gomory and Hu proved that the [Formula: see text] maxflow problems in an undirected network have at most n − 1 distinct solution values. We generalize their theorems in several ways. An interesting special case is that the O(n4) 2-commodity maxflow problems on an undirected network have at most [Formula: see text] distinct solution values. These results follow from general theorems on the number of distinct solution values to sets of optimization problems. We then show how the solutions can be compactly represented by a basis of the solution matrix A, where aij = 1 if solution j is feasible for problem i, and aij = 0 otherwise. For the special case of the 2-cut problem we also show how to construct such a representation efficiently.
Second-Order Sufficient Conditions in Nonsmooth Optimization
Authors: Chaney Robin W.
Published: October 2008

Second-order conditions are given which are sufficient to guarantee that a given point be a local solution to certain types of finite-dimensional nonsmooth nonlinear programming problems. Both unconstrained and constrained problems are considered. The conditions of the sufficiency theorems presented here are expressed in terms of the generalized gradients of nonsmooth analysis and (with one exception) certain second-order directional derivatives. These sufficiency theorems are complementary to some necessity theorems, which are proved elsewhere.
Additivizations of Nonadditive Measures
Authors: Gilboa Itzhak
Published: October 2008

The concept of an additivization of a nonadditive probability measure is introduced and studied. The relation to cooperative game theory is explored, and it is shown that, in many cases of interest, additivizations may be considered as a special type of semivalues.
Existence of Correlated Equilibria
Authors: Hart Sergiu , Schmeidler David
Published: October 2008

An elementary proof, based on linear duality, is provided for the existence of correlated equilibria in finite games. The existence result is then extended to infinite games, including some that possess no Nash equilibria.
Markov Chains with Rare Transitions and Simulated Annealing
Authors: Tsitsiklis John N.
Published: October 2008

We consider “approximate stationary” Markov chains in which the entries of the one-step transition probability matrix are known to be of different orders of magnitude and whose structure (that is, the orders of magnitude of the transition probabilities) does not change with time. For such Markov chains we present a method for generating order of magnitude estimates for the t-step transition probabilities, for any t. We then notice that algorithms of the simulated annealing type may be represented by Markov chains which are approximately stationary over fairly long time intervals. Using our results we obtain a characterization of the convergent “cooling” schedules for the most general class of algorithms of the simulated annealing type.
A Concentration Inequality for the K-Median Problem
Authors: Rhee Wansoo T. , Talagrand Michel
Published: October 2008

We use the theory of empirical processes to analyze a stochastic version of the K-median problem.
Continuous Location Theory Under Majority Rule
Authors: Durier R.
Published: October 2008

This paper studies, from a theoretical point of view, a single-facility location problem in a normed space. It is assumed that the facility has a finite or an infinite number of users and the location is selected under majority rule where, between two feasible locations, each user prefers the closer one. In general normed space three concepts of solutions—Condorcet points, Simpson points and plurality points—are geometrically described. In a two-dimensional space, practical methods of construction are given as well as the relationships between Condorcet points, plurality points, and medians; in the same framework, when the norm is polyhedral or the number of users is finite, it is proved that each Condorcet point is a solution to the associated Fermat-Weber problem.
Isotonic Median Regression: A Linear Programming Approach
Authors: Chakravarti Nilotpal
Published: October 2008

The isotonic median regression problem arises in statistics. It is known that the isotonic median regression problem, with respect to a complete order, may be solved by a “Pool Adjacent Violators” algorithm. In this paper we show that this algorithm is a dual method for solving a linear programming formulation of the problem. The linear programming approach provides additional insight into the algorithm as well as a simple proof of its validity. We also analyze the computational complexity of the algorithm and discuss its significance from the standpoint of linear programming theory.