bluuebunny/crossref_metadata_2025 huggingface dataset:
Sets of Generalized Complementarity Problems and P-Matrices
Authors: Habetler George J. , Kostreva Michael M.
Published: October 2008

The existence and uniqueness of solutions for a set of 2n simultaneous generalized linear complementarity problems (one per orthant of Rn) is studied. If all the complementary points are nondegenerate, each problem has a unique solution if and only if the coefficient matrix M is a P-matrix.
On the Monotone Symmetric Travelling Salesman Problem: Hypohamiltonian/Hypotraceable Graphs and Facets
Authors: Grötschel Martin
Published: October 2008

A graph G is called hypohamiltonian (hypotraceable) if it does not contain a hamiltonian cycle (chain) but if every vertex-deleted subgraph G − v contains a hamiltonian cycle (chain). It is shown that certain classes of these graphs induce facets of the monotone symmetric travelling salesman polytope, i.e. the convex hull of the incidence vectors of all tours and subsets of tours. These results indicate that it is quite unlikely that an explicit complete characterization of this polytope can be obtained.
Invariant Half-Lines of Nonexpansive Piecewise-Linear Transformations
Authors: Kohlberg Elon
Published: October 2008

It is shown that if f is a nonexpansive piecewise-linear mapping of Rm into itself, there exists a unique half-line that f maps into itself and such that restriction of f thereto is a translation. One easy consequence of this result is that there exists a unique m-vector α such that for every m-vector x, the sequence fn(x) − nα remains bounded. In particular, fn(x)/n converges to the same limit α, for all x. Also, f has a fixed point if and only if α = 0. These results are applied to give alternative proofs of several known facts concerning the maximum expected n-period reward in a finite Markov decision process.
An Analysis of Preemptive Multiprocessor Job Scheduling
Authors: Jaffe Jeffrey M.
Published: October 2008

The preemptive scheduling of a partially ordered set of tasks is studied. A class of scheduling heuristics is introduced, and the performance of schedules in this class is analyzed with respect to the least finishing time optimality criterion. If there are m processors, then the finishing time of any schedule in the class is at most [Formula: see text] times worse than optimal, independent of the speeds of the processors. Examples are given which indicate that there are schedules which may be as bad as [Formula: see text] times worse than optimal even for machines with one fast processor.
Locating an Isolated Global Minimizer of a Constrained Nonconvex Program
Authors: McCormick Garth P.
Published: October 2008

Conditions are given which verify the existence and determine the location of an isolated local constrained minimizer of a constrained nonconvex program. An exact formula is given for the amount by which the value of the objective function at some point differs from the value at that isolated point. Further conditions are given which ensure that the local minimizer is a global minimizer.
The Optimal Choice of a Subset of a Population
Authors: Vanderbei R. J.
Published: October 2008

We check a ranked population in random order. At each step we either accept or reject the observed sample. As a result we get a partition of the population into two parts: accepted and rejected. We are interested only in the case when all accepted samples are better than all rejected. Under this condition, we maximize the probability to obtain a fixed size k of the accepted part. An arbitrary gain function φ(k) is also considered.
Maximum Wealth Trees
Authors: Hwang F. K.
Published: October 2008

Associate a positive number, called an asset, to each nonterminal node of a t-ary tree, i.e., a rooted directed tree with outdegree t at each nonterminal node. The heritage of a node is the product of the assets of all its ancestors. The wealth of a tree is the sum of the heritages of its terminal nodes. For a given set of m assets, we give a simple construction for finding a t-ary tree with m nonterminal nodes and an assignment of the m assets to the m nonterminal nodes to achieve maximum wealth. Maximum wealth trees have applications in designing experiments to select a most probable event and in designing tournaments to identify a best player.
Convergent Algorithms for Minimizing a Concave Function
Authors: Van Thoai Nguyen , Tuy Hoang
Published: October 2008

For the problem of minimizing a concave function over a polytope a class of convergent algorithms is proposed, which is based upon a combination of the branch and bound technique with the cutting method developed earlier by H. Tuy.
Decompositions of Simplicial Complexes Related to Diameters of Convex Polyhedra
Authors: Provan J. Scott , Billera Louis J.
Published: October 2008

We introduce the property of k-decomposability for simplicial complexes which, if satisfied by the dual simplicial complex of a convex polyhedron, implies that the diameter of the polyhedron is bounded by a polynomial of degree k + 1 in the number of facets. These properties form a hierarchy, each one implying the next. The strongest, vertex decomposability, implies the Hirsch conjecture; the weakest is equivalent to shellability. We show that several cases in which the Hirsch conjecture has been verified can be handled by these methods, which also give the shellability of a number of simplicial complexes of combinatorial interest. We conclude with a strengthened form of the property of shellability which would imply the Hirsch conjecture for polytopes.
A 3-Sphere Counterexample to the Wv-Path Conjecture
Authors: Mani Peter , Walkup David W.
Published: October 2008

A triangulation D of the 3-sphere with 16 vertices and 90 3-simplices is exhibited. The cell complex D* dual to D has the property that each edge-path between two specified vertices visits some one of the 16 3-cells of D* at least twice. Thus D* is a counterexample to the Wv-path conjecture for S3 and consequently implies a counterexample to the Hirsch conjecture for S11 Previously known examples are of much larger size or dimension.
Erratum: The Principal Maxmin Matrix Transversal Strategy
Authors: Kevorkian Aram K.
Published: October 2008

Erratum to Kevorkian, A. K. 1979. The principal maxmin matrix transversal strategy. Math. Oper. Res. 4 274–290.
A Modified Integer Labeling for Complementarity Algorithms
Authors: Reiser Peter M.
Published: October 2008

Nonlinear complementary problems can be solved by algorithms based on the principle of simplicial approximation. We present such an algorithm that allows the choice of an arbitrary starting point without using an artificial labeling or an extra dimension. Furthermore the relation between the grid size of the triangulation and the accuracy of an approximate solution is investigated, and it is shown that a combination of the algorithm with Newton-steps yields better accuracy. Finally the algorithm is adapted for solving systems of equations.
Minimizing Maximum Lateness in a Two-Machine Open Shop
Authors: Lawler E. L. , Lenstra J. K. , Rinnooy Kan A. H. G.
Published: October 2008

We consider the problem of scheduling independent jobs in a two-machine open shop so as to minimize the maximum lateness with respect to due dates for the jobs. For the case in which preemption is allowed, a linear-time algorithm is presented. For the nonpreemptive case, NP-hardness is established.
Analysis of Greedy Solutions for a Replacement Part Sequencing Problem
Authors: Friesen D. K. , Deuermeyer B. L.
Published: October 2008

This paper considers the problem of sequencing the installation of replacement parts for the repeated repair of a machine consisting of two working parts. A finite inventory of spares is initially available for each type of part. Each spare has a known (deterministic) field life, and spares of each type may have different field lives. The inventories are eventually depleted since no replacement or repairs of parts occur. The primary objective is to obtain a sequencing policy which minimizes the total number of installations (replacements). This problem is a special case of many opportunistic replacement problems and is called a “build” problem. The motivation for this work is based on the maintenance of modular gas turbine aircraft engines used by domestic airlines and the U.S. Air Force. We show this build problem is NP-hard which indicates the necessity of efficient heuristic solution procedures. This paper considers several “greedy” type algorithms based on grouping parts according to exact matching of field lives. Then, a generalization is presented which allows approximate matches. The focus of the analysis is to obtain tight worst case bounds on the number of replacements obtained by each of the greedy algorithms.
The Lexicographic Kernel of a Cooperative Game
Authors: Yarom Moshe
Published: October 2008

The purpose of this paper is to compare the nucleolus and the lexicographic kernel, and find analogous properties. It is shown that the lexicographic kernal has, like the nucleolus, the following properties: It lies in the intersection of the kernel and the least core, and has a converging dynamic procedure similar to Justman's procedure for the nucleolus. The lexicographic kernel does not always consist of a unique point as the nucleolus. However it is continuous as a set valued function. On the other hand, the lexicographic kernel is a “geometrical locus” in the nonempty ϵ-core, whereas the nucleolus is not.
Duality for Multiple Objective Convex Programs
Authors: Brumelle Shelby
Published: October 2008

A duality theory for the problem of finding the properly efficient values of a multiple objective convex program is obtained using arguments and concepts analogous to those used by Rockafellar for scalar valued problems. A key result is that x̄ minimizes a convex, vector valued function f if and only if there is a “zero-like” subgradient of f at x̄. Consequently, if a vector valued convex program with a given perturbation is represented by a convex bifunction, then the properly efficient values of the program are equal to the perturbation function evaluated at zero-like perturbations. A dual program is defined in terms of the adjoint bifunction. Certain closure conditions insure the absence of a duality gap. The dual variables are matrices with the interpretation that the (i, j)-th element is the value of the ith resource in terms of the jth objective.

A concept of optimality called Isermann efficiency is introduced and compared with efficiency and proper efficiency. Isermann efficiency generalizes a concept from Isermann's work on multiple objective linear programs.
Stationary Distributions of Flows in Jackson Networks
Authors: Labetoulle J. , Pujolle G. , Soula C.
Published: October 2008

This paper analyzes several queueing systems with feedback. We obtain the stationary distribution of the interinput, interoutput and inter feedback times for a M/M/1 queue with feedback. Then we show the equality of the distributions of the interinput times and interoutput times for any queue in a general Jackson network.
A Decomposition Algorithm for Sequencing with General Precedence Constraints
Authors: Sidney Jeffrey B.
Published: October 2008

Many important unconstrained job sequencing problems for which optimal algorithms exist satisfy the adjacent job interchange property. In recent years, a more general property, the adjacent sequence interchange property, has been identified and shown to be a sufficient condition for the existence of efficient algorithms for sequencing problems with series-parallel precedence constraints. In this paper, additional properties are defined which are sufficient to prove the existence of decomposition algorithms for general precedence structures. These results are applicable to several problems, including the two-machine maximum flow time problem, the maximum cumulative cost problem, the least cost fault detection problem, and the total weighted exponential completion time problem, and represent an extension of Sidney's results on the weighted completion time problem.
A Column Generation Technique for the Computation of Stationary Points
Authors: Pang Jong-Shi
Published: October 2008

In two recent papers, Eaves showed that Lemke's algorithm can be used to compute a stationary point of an affine function over a polyhedral set. This paper proposes an alternative method which is based on parametric principal pivoting. The proposed method involves solving systems of linear equations and parametric linear subprograms over the given polyhedral set. An obvious advantage of the method is that any special structure of the polyhedral set can be exploited profitably in the solution of the subprograms.
Proof of Convergence for a Modification of Goldfarb's Algorithm
Authors: Fischer Jürgen
Published: October 2008

A variable metric algorithm for minimization problems under linear inequality constraints similar to that of Goldfarb is constructed and shown to be superlinearly convergent.
A Decomposition Methodology and a Class of Algorithms for the Solution of Nonlinear Equations
Authors: Kevorkian Aram K.
Published: October 2008

In this paper we develop a decomposition methodology to find a solution of a system of nonlinear equations. The decomposition methodology is based on the matrix theoretic notion of nonzero transversal and the graph theoretic notion of minimal essential set. This decomposition methodology gives rise to a class of three iterative methods each of which uses a derivative matrix whose order is equal to the cardinality of the minimal essential set. We prove that the iterative methods are types of the Newton method. For the case of a system of linear equations, we show that the iterative methods are combinations of the generalized Gaussian elimination and the Newton method.
A Stochastic Solution Concept for n-Person Games
Authors: Packel Edward W.
Published: October 2008

Let X be a set of outcomes among which a set of N players, each having a preference relation on X, must choose. Let v: 2N\/Ø} → 2X be a game in generalized characteristic function form, where v(C) denotes the set of outcomes that a coalition C can guarantee its members regardless of actions by players outside of C. By letting c(x, y) denote the number of minimal coalitions via which y is directly accessible from x, a Markov chain model of outcome selection is developed. By establishing convergence results for both finite and spatial (X ⊆ Rm) outcome cases, a probability measure on X is obtained and referred to as the stochastic solution of the game. After presenting some initial results on the dependence of the stochastic solution on the initial outcome distribution, it is shown under reasonable assumptions that a (strong) core, if it exists, must occur with probability one. Generally, the results obtained have natural interpretations and proofs using the language and theory of Markov chains. Finally, some examples and previous experimental results are considered in terms of the model. Stochastic solution values obtained and their agreement with available experimental values appear to be very encouraging.
A Nonorthogonal Fourier Expansion for Conic Decomposition
Authors: Barzilai J. , Ben-Tal A.
Published: October 2008

The problem considered is that of constructing the decomposition of a vector in a Hilbert space into two orthogonal components; one (the “projection”) in a given cone, and the other in the polar cone. The projection z* can be expressed as a Fourier type expansion. An algorithm for constructing this expansion is given, and shown to converge to z*.
Complete Convergence of Short Paths and Karp's Algorithm for the TSP
Authors: Steele J. Michael
Published: October 2008

Let Xi, 1 ≤ i < ∞, be uniformly distributed in [0, 1]2 and let Tn be the length of the shortest closed path connecting {X1, X2, …, Xn}. It is proved that there is a constant 0 < β < ∞ such that for all ϵ > 0 [Formula: see text] This result is essential in justifying Karp's algorithm for the traveling salesman problem under the independent model, and it settles a question posed by B. W. Weide.
Learning Algorithms for Two-Person Zero-Sum Stochastic Games with Incomplete Information
Authors: Lakshmivarahan S. , Narendra Kumpati S.
Published: October 2008

This paper investigates conditions under which two learning algorithms playing a zero-sum sequential stochastic game would arrive at optimal pure strategies. Neither player has knowledge of either the pay-off matrix or the choice of strategies available to the other and both players update their own strategies at every stage entirely on the basis of the random outcome at that stage. The proposed learning algorithms are shown to converge to the optimal pure strategies when they exist with probabilities as close to 1 as desired.
Flows in Queueing Networks: A Martingale Approach
Authors: Walrand J. , Varaiya P.
Published: October 2008

This paper applies the filtering theory for point process observations to the analysis of flows in networks. An abstract model for the study of Markovian queueing systems is developed and used to derive the filtering equations satisfied by the conditional probability distribution of the state given the past of an observed set of flows. These filtering equations are used to obtain a necessary and sufficient condition for that observation to be independent of the value of the state of the system at any time. This approach also yields a probabilistic interpretation of a necessary condition for a given flow in a multi-class Jackson network to be Poisson.

These results are combined to give a proof of the “loop criterion” for single-class Jackson network and to show that this criterion does not apply to multi-class networks. Examples of loop-free Jackson networks are given for which some of the flows are not Poisson.
Multivariate Classes of Life Distributions in Reliability Theory
Authors: Block Henry W. , Savits Thomas H.
Published: October 2008

Four classes of life distributions which have been useful in describing aging where systems are assumed to have independent univariate component lifetimes are: (1) the increasing failure rate (IFR) class; (2) the increasing failure rate average (IFRA) class; (3) the new better than used (NBU) class; and (4) the new better than used in expectation (NBUE) class. These classes together with multivariate analogs of the IFR and IFRA classes are reviewed and discussed. An up to date survey of the literature on this topic is included. New multivariate definitions of the NBU and NBUE classes are introduced.
Law of Large Numbers for Random Sets and Allocation Processes
Authors: Artstein Zvi , Hart Sergiu
Published: October 2008

In this paper we establish a strong law of large numbers for unbounded random sets, and then apply it to an optimization problem arising in allocation processes under uncertainty.
Constrained Optimization of Functionals with Search Theory Applications
Authors: Stromquist Walter R. , Stone Lawrence D.
Published: October 2008

We find necessary and sufficient conditions for maximizing a wide class of nonlinear, nonseparable functionals under separable constraints. The crucial restriction on the functionals is that they have a Gateaux differential which is a linear functional with a kernel. The conditions obtained can be applied to a large variety of optimal search problems involving moving targets when effort is infinitely divisible in space. Moreover, the conditions have been used to construct very efficient algorithms for solving these problems. It is conjectured that these results are useful in a general class of optimization problems that extend well beyond the search theory examples presented in this paper.
Closure in Independence Systems
Authors: Matthews Laurence
Published: October 2008

The set of feasible solutions of a discrete optimization problem can, in many cases, be represented as an independence system, or hereditary system of sets. It is often the case that this system has some structure which may be exploited in the solution of the problem. For example, in the case of a matroid a “greedy algorithm” can be used; this situation, however, occurs rarely in practice. We investigate here the abstract structure of independence systems using concepts from matroid theory, in particular analogues of matroid closure. Two functions are defined which coincide with the ususal closure operator if the independence system is a matroid, and for each of these functions an axiomatic characterization is given. In each case this consists of a weakened form of one of the matroid closure axioms with the other three remaining unchanged. Finally, duality is considered and this leads to characterizations, in terms of closure operators and paintings, of those independence systems where all bases have the same cardinality: these include the “Travelling Salesman” and “Acyclic Subgraph” independence systems.
Algebraic Linear Programming
Authors: Frieze A. M.
Published: October 2008

The algebraic approach to network-flow problems discussed by Burkard and Zimmermann (Burkard, R. E., U. Zimmermann. 1977. Weakly admissible transformations for solving algebraic assignment and transportation problems. Balinski and Padperg, eds. Report 1977-8, Mathematische Institut der Universitat Zu Koln (1977). To appear in Math. Prog. Stud.) is generalized to linearly-constrained problems. The aim is to choose a real nonnegative n-vector N that minimizes c(x) subject to finitely many linear equations with positive right-hand sides where the range S of c(·) is totally ordered and c satisfies other algebraic assumptions. This structure includes lexicographic linear programs in which c(x) = Cx where C is a matrix with n lenieographically-nonnegative columns and S is totally ordered by the lexicographic order. This problem in turn includes ordinary and bottleneck linear programs. A primal-dual method is given for solving these “algebraic” linear programs.
Locating Centers on a Tree with Discontinuous Supply and Demand Regions
Authors: Tamir Arie , Zemel Eitan
Published: October 2008

Consider a tree T = (N, E) with “supply” and “demand” regions Σ and Δ, each composed of a finite number of disjoint, closed and connected subregions of T, some of which may possibly consist of just one point. Given an integer p, we seek a collection of p “centers” x1, …, xp ∈ Σ, which minimize the expression maxy∈δ mini=1,…,pd(y, xi). We present a polynomial algorithm for this problem. Its running time is bounded by O(n log2n) if either Δ or Σ is discrete, and by O(n min|p log2n,n log p|) if both sets contain at least one full edge.
Sojourn Times in Queueing Networks
Authors: Melamed Benjamin
Published: October 2008

We consider a queueing network with types of customers. Poisson arrivals, type dependent routing and state dependent service. A number of stochastic aspects relating to sojourn times are investigated. Included are limiting state distributions imbedded at customer move times, mean sojourn times, and sojourn time distributions along overtake-free paths. It is shown that Reich's results extend to overtake-free paths yielding limiting sojourn time distributions which correspond to the sum of exponential independent stages of sojourn in individual nodes. The analysis is bused solely on considerations of population distributions through conditioning on customers' itineraries in the network.
Queue Disciplines in Heavy Traffic
Authors: Kingman J. F. C.
Published: October 2008

A general method of analyzing the behavior in heavy traffic of queues with different impartial queue disciplines is described. There are many possible limiting waiting time distributions though all are mixtures of negative exponentials. The exponential distribution itself, however, shows a degree of robustness to departures from the “first come first served” discipline.
A Partial Characterization of a Class of Matrices Defined by Solutions to the Linear Complementarity Problem
Authors: Doverspike R. D. , Lemke C. E.
Published: October 2008

In this paper we analyze the class of matrices, Q0, characterized as all n × n matrices, M, for which the linear complementarity problem, w = Mz + q, w, z ≥ 0, w′z = 0, has a solution whenever q is feasible. The method is to analyze the faces of the linear cone. Cone[I, −M] where I is the n × n identity. Essentially, a labelling requirement for the faces is shown necessary for M to be in Q0. With proper restrictions and nondegenerate assumptions sufficiency is also shown. These results arc related to the signs of the minors of M and some conjectures in this area are also discussed.
Computing Maximal “Polymatroidal” Network Flows
Authors: Lawler E. L. , Martel C. U.
Published: October 2008

In the “classical” network flow model, flows are constrained by the capacities of individual arcs. In the “polymatroidal” network flow model introduced in this paper, flows are constrained by the capacities of sets of arcs. Yet the essential features of the classical model are retained: the augmenting path theorem, the integral flow theorem and the max-flow min-cut theorem arc all shown to yield to straightforward generalization. We describe a maximal flow algorithm which finds augmenting paths by labeling arcs instead of nodes, as in the case of the classical model. As a counterpart of a known result for the classical model, we prove that the number of augmentations required to achieve a maximal value flow is bounded by the cube of the number of arcs in the network, provided each successive augmentation is made along a shortest augmenting path, with ties between shortest paths broken by lexicography.
Finite-Degree Utility Independence
Authors: Fishburn Peter C. , Farquhar Peter H.
Published: October 2008

When u is a von Neumann-Morgenstern utility function on X × Y, Y is “utility independent” of X if u can be written as u(x, y) = f(x)g(y) + a(x) with f positive. This paper introduces a fundamental extension of utility independence that is based on induced indifference relations over gambles on one factor when the level of the other factor is fixed. It is proved that Y is “degree-n utility independent” of X if and only if u can be written as u(x, y) = ft(x)gt(y) + ⋯ + fn(x)gn(y) + a(x) and cannot be written in a similar way with fewer than n products of single-factor functions. A similar theorem holds when the roles of Y and X are interchanged, it follows that if Y is degree-n utility independent of X, then X is degree-m utility independent of Y for some m ∈ (n − 1, n, n + 1); it is then shown that u can be represented in terms of n conditional utility functions on Y, m conditional utility functions on X, and at most (n + 1)(m + 1) scaling constants.
Discrete Sequential Search with Positive Switch Cost
Authors: Lössner Udo , Wegener Ingo
Published: October 2008

Suppose one object is hidden in one of n boxes according to a known probability distribution p(1), …, p(n). The boxes are to be searched sequentially. The probability of overlooking the object if we search box k and if the object is in box k is denoted by q(k). The cost of a search of box k amounts to c(k). If we decide to search box k directly after box k′ we have to pay some extra cost called switch cost: T(k′, k). The problem is—under some reasonable assumptions—to construct a strategy with minimal expected cost. If T ≡ 0 the problem has a well-known solution. Unfortunately there are many reasons which establish the conjecture that there does not exist an easy construction rule for optimal strategies in the general case. We give necessary and sufficient conditions for the existence of optimal strategies which are ultimately periodic (u.p.). Since we state bounds on the length not only of the transient phase but also of the period of optimal u.p. strategies we may construct these optimal strategies by comparing finitely many strategies (if optimal u.p. strategies exist). We prove some other results to reduce the number of strategies which we have to compare. At last we present a numerical example.
A Class of Continuous Network Flow Problems
Authors: Anderson E. J. , Nash P. , Philpott A. B.
Published: October 2008

The solution in discrete time of the problem of maximizing the flow in a network with time-varying are capacities and storage at the nodes is a straightforward extension of the static case. In this paper the problem is formulated and solved in continuous time. A continuous version of the Ford-Fulkerson theorem is proved, and an analogue of the labelling algorithm developed. An example is given to clarify some of the ideas of the paper and the duality theory for this problem is discussed.
Continuity Theorems in Stochastic Control Problems
Authors: Yamada Keigo
Published: October 2008

For some stochastic control systems described by stochastic integral equations where the admissible control class is a set of uniformly equi-Lipschitz continuous functions, it is shown that, under suitable conditions, the optimal output process is continuously dependent on the input process in the sense of weak convergence.
Growth Optimality for Branching Markov Decision Chains
Authors: Rothblum Uriel G. , Whittle Peter
Published: October 2008

This paper considers a (multiplicative) process called branching Markov decision chains in which the output at the end of the Nth period equals the product of N nonnegative matrices chosen at the beginning of periods 1, …, N, respectively, times a positive (fixed) terminal reward vector. It is assumed that the above transition matrices are drawn out of a finite set of matrices given in product form (i.e., the rows of the matrices can be selected independently out of finite sets of nonnegative row vectors). For each coordinate s we define the geometric and algebraic growth rates, respectively, of the sth coordinate of the stream of output. These growth rates are defined so that the magnitude of the corresponding sequence is of the order αNNk where α is the geometric growth rate and k is the algebraic growth rate. The main result of this paper is the constructive establishment of the existence of a transition matrix whose repeated use will guarantee, for each coordinate, the achievement of the best geometric growth rate and the best algebraic growth rate subject to the geometric growth rate at maximum, among all potential sequences of transition matrices.
On Knapsacks, Partitions, and a New Dynamic Programming Technique for Trees
Authors: Johnson D. S. , Niemi K. A.
Published: October 2008

Let G be an acyclic directed graph with weights and values assigned to its vertices. In the partially ordered knapsack problem we wish to find a maximum-valued subset of vertices whose total weight does not exceed a given knapsack capacity, and which contains every predecessor of a vertex if it contains the vertex itself. We consider the special case where G is an out-tree. Even though this special case is still NP-complete, we observe how dynamic programming techniques can be used to construct pseudopolynomial time optimization algorithms and fully polynomial time approximation schemes for it. In particular, we show that a nonstandard approach we call “left-right” dynamic programming is better suited for this problem than the standard “bottom-up” approach, and we show how this “left-right” approach can also be adapted to the case of in-trees and to a related tree partitioning problem arising in integrated circuit design. We conclude by presenting complexity results which indicate that similar success cannot be expected with either problem when the restriction to trees is lifted.
Team Guessing with Lacunary Information
Authors: Witsenhausen H. S.
Published: October 2008

Let E be an event of probability q and let U1, …, Un be independent random variables. There are n observers, the ith observing the n-1 random variables other than Ui. Each observer must guess whether E occurred. Then if pi is the probability of error of observer i, one has [Formula: see text] where p = max(q, 1 − q), and this bound is sharp.

One application is related to a coding theorem. The coding is used to reduce degradation when data transmission is split over n parallel channels, any one of which might have broken down.

The result also has a more symmetric corollary which can be stated as a probabilistic inequality of an unusual type.
Stimulating Prices in a Stochastic Model of Resource Allocation
Authors: Kennedy D. P.
Published: October 2008

The optimal allocation for a general stochastic model for the sequential allocation of a resource between consumption and production is derived. A system of prices for the resource which stimulates this optimal allocation is identified. These prices are shown to be the product of a certain martingale and a random discount factor.
Polarities Given by Systems of Bilinear Inequalities
Authors: Aráoz D. Julián , Edmonds Jack , Griffin Victor J.
Published: October 2008

We extend the concept of polar pairs of cones to polyhedra using binary relations given by systems of bilinear inequalities. In particular we consider those which give natural generalizations of the theory of blocking and antiblocking of Fulkerson. These extensions preserve the important relations between vertices and facets of polar pairs
Multi-Stage Planning and the Extended Linear-Quadratic-Gaussian Control Problem
Authors: Lagarias J. C. , Aminzadeh F.
Published: October 2008

Multi-stage planning processes arise in many situations in operations research and economics. The purpose of the planning process is to adapt to a future described by certain state variables x(k). This paper considers the problem of finding optimal forecasts for the state variables which explicitly take account of a cost tradeoff between costs associated to errors in predicting the values of the state variables and costs associated with changes in forecasts for a particular time k made at successive time periods k1, k2. That is, there is a tradeoff between the accuracy of individual forecasts x̃(k ∣ k2) for x(k) and the stability of successive forecasts x̃(k ∣ k1) and x̃(k ∣ k2). This paper gives an exact solution in the case where the state variables x̃(k) are generated by a Gaussian linear system and the cost function is quadratic plus linear in the state variables and forecasts. In this case the optimal forecasts are matrix weighted linear combinations of Kalman filter estimates, with weights depending only on the loss function. In the special case that all costs associated with a change in forecasts occur in the period the change is made, these weights have a simple recursive form. This problem is a special case of a stochastic control problem we call the extended linear-quadratic-Gaussian control problem.
Preservation of Life Distribution Classes Under Reliability Operations
Authors: Lén Ramón V. , Lynch James
Published: October 2008

Let G be a continuous life distribution with support [0, c] and consider the following classes of life distributions: 𝒷 = {F: F(0) = 0 and G−1F is convex on (0, F−1(1))}, 𝒱 = {F: G−1F is concave on (0, ∞)}, 𝒻 = {F: G−1F(θx) ≤ θG−1F(x) for 0 < θ < 1, 0 < x < F−1(l)}, and 𝒜 = {F: G−1F(θx) ≥ G−1F(x) for 0 < θ < 1, 0 < x < ∞}. In the case where G is exponential, 𝒷, 𝒱, 𝒻, and 𝒜 are, respectively, the classes of life distributions with increasing failure rate, decreasing failure rate, increasing failure rate average, and decreasing failure rate average. In this paper we study the closure properties of the classes 𝒷, 𝒱, 𝒻, and 𝒜 under the formation of coherent systems, convolutions, and mixtures. Our results can be used to obtain information about the reliability of systems of components on the basis of component data.
Global Minimization of a Linearly Constrained Concave Function by Partition of Feasible Domain
Authors: Rosen J. B.
Published: October 2008

The problem of minimizing a concave function subject to linear inequality constraints may have many local solutions. Therefore, finding the global constrained minimum is a computationally difficult problem.

A computational method is described which finds the global minimum of a smooth concave function over a polyhedron in Rn. The feasible domain is partitioned into a rectangular domain, which can be excluded from further consideration, and r ≤ 2n subdomains, at least one of which contains the global minimum. A known algorithm can be applied sequentially (or in parallel) to each of these r subdomains to compute the global minimum.

A method is also presented (Appendix B) for the construction of nontrivial test problems for which the global minimum point is known. Given an arbitrary polyhedron and a selected vertex, it is shown how to determine a concave quadratic function (generally with many local minima) with its global minimum at the selected vertex.
An Algorithm for Solving the General Bilevel Programming Problem
Authors: Bard Jonathan F.
Published: October 2008

The conflict that naturally arises in a hierarchical system can often be modeled as a multistage optimization problem. This paper considers the sequential uncooperative problem in which two decision makers wish to maximize their own objective functions over a feasible region defined by interactive strategy sets. The resultant problem is known as the bilevel program. Such programs are inherently nonconvex and resistant to standard nonlinear programming solution techniques such as piecewise linearization and convex underestimating envelopes. Alternatively, a grid search algorithm is offered which exhibits the desirable property of monotonicity. The algorithm is based on two sets of necessary conditions previously developed and combined here to provide an operational check for stationarity and local optimality. Potential solutions are obtained from a parameterized master program whose feasible region approximates that of the original problem. As the one-dimensional parameter is varied over the unit interval and the master problem solved, a nondecreasing sequence of lower bounds to the first decision maker’s objective function is produced. If the solution to the original problem is stable under small perturbations, the sequence is shown to converge to the global optimum. A discussion of the computational requirements follows the presentation of the algorithm.
Combinatorial Optimization with Rational Objective Functions: A Communication
Authors: Ahuja R. K. , Batra J. L. , Gupta S. K.
Published: October 2008

Megiddo (Megiddo, N. 1979. Combinatorial optimization with rational objective functions. Math. Oper. Res. 4 414–424.) has proposed an algorithm to solve a class of combinatorial optimization problems with rational objective functions in polynomial time. The minimum ratio path problem is claimed to be one such problem. This claim is not correct as indicated below.
The Complexity of Vertex Enumeration Methods
Authors: Dyer M. E.
Published: October 2008

The computational complexity of problems relating to the enumeration of all the vertices of a convex polyhedron defined by linear inequalities is examined. Several published approaches are evaluated in this light. A new algorithm is described, and shown to have a better complexity estimate than existing methods. Empirical evidence supporting the theoretical superiority is presented. Finally vertex enumeration is discussed when the space containing the polyhedra is of fixed dimension and only the size of the inequality system is permitted to vary.
An Axiomatic Characterization of Multistate Coherent Structures
Authors: Borges Wagner De Souza , Rodrigues Flávio Wagner
Published: October 2008

Mathematical models for multistate reliability systems of multistate components have been proposed by Barlow and Wu (Barlow, R. E., A. S. Wu. 1978. Coherent systems with multistate components. Math. Oper. Res. 3 275–281.), El-Neweihi et al. (El-Neweihi, E., F. Proschan, J. Sethuraman. 1978. Multistate coherent systems. J. Appl. Probab. 15 675–688.) and Griffith (Griffith, W. S. 1980. Multistate reliability models. J. Appl. Probab. 17 735–744.). Unlike the approach used by Barlow and Wu, the other authors preferred to establish their classes of models through sets of axioms extending the early binary notions and containing as special cases the class of models suggested by Barlow and Wu. Since the Barlow and Wu approach is set theoretic and the model definition is essentially qualitative, a question of interest concerns its axiomatic characterization among larger classes of models. In this paper such a characterization is established that relates the Barlow and Wu models to the other classes of models introduced later.
Instantaneous Control of Brownian Motion
Authors: Harrison J. Michael , Taksar Michael I.
Published: October 2008

A controller continuously monitors a storage system, such as an inventory or bank account, whose content Z = {Zt,t≥0} fluctuates as a (μ, σ2) Brownian motion in the absence of control. Holding costs are incurred continuously at rate h(Zt). At any time, the controller may instantaneously increase the content of the system, incurring a proportional cost of r times the size of the increase, or decrease the content at a cost of l times the size of the decrease. We consider the case where h is convex on a finite interval [α, β] and h = ∞ outside this interval. The objective is to minimize the expected discounted sum of holding costs and control costs over an infinite planning horizon.

It is shown that there exists an optimal control limit policy, characterized by two parameters a and b (α ≤ a < b ≤ β). Roughly speaking, this policy exerts the minimum amounts of control sufficient to keep Zt ∈ [a, b] for all t ≥ 0. Put another way, the optimal control limit policy imposes on Z a lower reflecting barrier at a and an upper reflecting barrier at b. The optimality of a particular control limit policy is proved directly, with heavy reliance on the change of variable formula for semimartingales. We do not give a full-blown algorithm for construction of the optimal control limits, but a computational scheme could easily be developed from our constructive proof of existence.
Corrigendum: Algebraic Linear Programming
Authors: Frieze Alan
Published: October 2008

Corrigendum to Frieze, A. M. 1982. Algebraic linear programming. Math. Oper. Res. 7 172–182.
Preference Convex Unanimity in Multiple Criteria Decision Making
Authors: Hazen Gordon B.
Published: October 2008

The approach which results in the definition of stochastic dominance orders for risky decision making can also be applied to the nonrisky case, that is, one may postulate that alternative x dominates alternative y if x is preferred to y by every possible decision maker with specified preference characteristics. One such “unanimity” order is the standard componentwise vector order of multiple objective optimization. In this paper, a unanimity order is constructed based upon characteristics of preference convexity in conjunction with finitely many elicited preference responses. Since the new order properly includes the vector order, the corresponding efficient frontier may be smaller.
Integer Programming with a Fixed Number of Variables
Authors: Lenstra H. W.
Published: October 2008

It is shown that the integer linear programming problem with a fixed number of variables is polynomially solvable. The proof depends on methods from geometry of numbers.
Constructing Majority Paths Between Arbitrary Points: General Methods of Solution for Quasi-Concave Preferences
Authors: McKelvey Richard D.
Published: October 2008

A series of recent articles has established that in continuous alternative spaces where voter preferences are representable by continuous utility functions, there generally exist majority paths between any two points in the space. In this paper, the problem of constructing such paths is dealt with. It is shown that if the dimensionality of the underlying alternative space is at least three, the problem can be decomposed into a series of smaller, limited horizon problems. These smaller problems can then be formulated as several independent convex programming problems, which could be solved by standard methods.
A Newton-Type Algorithm for the Solution of the Implicit Programming Problem
Authors: Feinstein C. D. , Oren S. S.
Published: October 2008

A second-order algorithm is presented for the solution of the implicit programming problem. The implicit programming problem is a mathematical programming problem that has as its solution the optimal steady-states of an optimal control problem defined on an infinite horizon. The algorithm is shown to be a variant of Newton's method for solving a fixed-point problem defined implicitly by the implicit programming problem. Local and global convergence properties of the algorithm are briefly discussed.
Lipschitz Behavior of Solutions to Convex Minimization Problems
Authors: Aubin Jean-Pierre
Published: October 2008

We derive the Lipschitz dependence of the set of solutions of a convex minimization problem and its Lagrange multipliers upon the natural parameters from an inverse function theorem for set-valued maps. This requires the use of contingent and Clarke derivatives of set-valued maps, as well as generalized second derivatives of convex functions.
On The Marginal Function in Nonlinear Programming
Authors: Gollan Bernhard
Published: October 2008

For several types of finite or infinite dimensional optimization problems the marginal function (or optimal value function) is characterized by different local approximations such as generalized gradients, generalized directional derivatives, directional Hadamard or Dini derivatives. We give estimates for these terms which are determined by multipliers satisfying necessary optimality conditions. When the functions which define the optimization problem are more than once continuously differentiable, then higher order necessary conditions are employed to obtain refined estimates for the marginal function. As a by-product we give a new equivalent formulation of Clarke's multiplier rule for nonsmooth optimization problems. This shows that the set of all multipliers satisfying these necessary conditions is the union of a finite number of closed convex cones.
A Note on Approximation Schemes for Multidimensional Knapsack Problems
Authors: Magazine Michael J. , Chern Maw-Sheng
Published: October 2008

Polynomial and fully polynomial approximation algorithms for single-dimensional knapsack problems have been extensively studied and a number of such algorithms constructed. This note shows that the problem of finding a fully polynomial approximation algorithm for multidimensional knapsack problems is NP-hard.
Constrained Undiscounted Stochastic Dynamic Programming
Authors: Hordijk A. , Kallenberg L. C. M.
Published: October 2008

In this paper we investigate the computation of optimal policies in constrained discrete stochastic dynamic programming with the average reward as utility function. The state-space and action-sets are assumed to be finite. Constraints which are linear functions of the state-action frequencies are allowed. In the general multichain case, an optimal policy will be a randomized nonstationary policy. An algorithm to compute such an optimal policy is presented. Furthermore, sufficient conditions for optimal policies to be stationary are derived.

There are many applications for constrained undiscounted stochastic dynamic programming, e.g., in multiple objective Markovian decision models.
On Stationary Strategies in Countable State Total Reward Markov Decision Processes
Authors: van der Wal Jan
Published: October 2008

This paper deals with total reward Markov decision processes with countable state space. Various partial results from the literature are connected and extended in the following theorem. If in each state where the value is nonpositive a conserving action exists then there exists a stationary strategy f which is uniformly nearly optimal in the following sense: v(f) ≥ v* − ϵu*, where u* is the value of the problem if only the positive rewards are counted.

Further, the following result is established: if an optimal strategy exists then also an optimal stationary strategy exists.