bluuebunny/crossref_metadata_2025 huggingface dataset:
Integer Solution for Linear Complementarity Problem
Authors: Chandrasekaran R. , Kabadi S. N. , Sridhar R.
Published: October 2008

We consider the problem of finding an integer solution to a linear complementarity problem. We introduce the class I of matrices for which the corresponding linear complementarity problem has an integer complementary solution for every vector, q, for which it has a solution. Strong principal unimodularity forms a sufficient condition for inclusion in the class I. It is also shown to be necessary for some well-known classes of matrices, including the class of positive semidefinite matrices. This is used in deriving necessary and sufficient conditions for a convex quadratic program to have an integer optimal solution for all b and c for which it has an optimal solution. Characterizations are also derived for some other well-known classes of matrices in linear complementarity to belong to the class I. In the end, a peeling algorithm for finding integer solution for linear complementarity problems is given and related results are derived.
Approximating Extreme Points of Infinite Dimensional Convex Sets
Authors: Cross William P. , Romeijn H. Edwin , Smith Robert L.
Published: October 2008

The property that an optimal solution to the problem of minimizing a continuous concave function over a compact convex set in ℝn is attained at an extreme point is generalized by the Bauer Minimum Principle to the infinite dimensional context. The problem of approximating and characterizing infinite dimensional extreme points thus becomes an important problem. Consider now an infinite dimensional compact convex set in the nonnegative orthant of the product space ℝ∞. We show that the sets of extreme points EN of its corresponding finite dimensional projections onto ℝN converge in the product topology to the closure of the set of extreme points E of the infinite dimensional set. As an application, we extend the concept of total unimodularity to infinite systems of linear equalities in nonnegative variables where we show when extreme points inherit integrality from approximating finite systems. An application to infinite horizon production planning is considered.
Global Error Bounds for Convex Multifunctions and Applications
Authors: Li Wu , Singer Ivan
Published: October 2008

We give some results on the existence of global error bounds for convex multifunctions between normed linear spaces (until the present, only some results on local error bounds have been known in this general setting). As applications we obtain, among others, improvements of a theorem of Robinson on global error bounds for convex inequalities, of a result of Luo and Tseng on uniform boundedness of the Hoffman constants for linear inequalities and equalities, and of Lotov's result on pointwise Lipschitz continuity of the solution sets of linear inequalities, with respect to data perturbations.
Level-Crossing Properties of the Risk Process
Authors: Stadje Wolfgang
Published: October 2008

For the classical risk process R(t) that is linear increasing with slope 1 between downward jumps of i.i.d. random sizes at the points of a homogeneous Poisson process we consider the level-crossing process C(x) = (L(x), (Ai (x), Bi (x))1≤ i ≤ L ( x )), where L(x) is the number of jumps from (x, ∞) to (−∞, x] and Ai (x) (Bi (x)) are the distances from x to R(t) after (before) the ith jump of this kind. It is shown that if R(·) has a drift toward infinity, C(·) is a stationary Markov process; its transition probabilities are determined. As an application we derive the expected value E(L(x)L(x + y)).
Structural Properties of Lot Streaming in a Flow Shop
Authors: Glass C. A. , Potts C. N.
Published: October 2008

Lot streaming is the process of splitting a given lot or job to allow the overlapping of successive operations in multi-stage production systems, thereby reducing the makespan of the corresponding schedule. This paper considers the problem of finding sublot sizes to minimize the makespan for a single job in an m-machine flow shop. On each machine, the job is to be partitioned into a given number of sublots, and sublot sizes are the same on each machine. We introduce the concept of machine dominance, and propose an algorithm to reduce the problem so that only dominant machines are considered explicitly. After defining a network representation in which it is required to find the shortest critical path length, we identify the structure of critical paths for optimal sublot sizes. Knowledge of this structure considerably reduces the search for an optimal solution, which we illustrate by presenting algorithms for finding optimal sublot sizes.
Minimization of Half-Products
Authors: Badics T. , Boros E.
Published: October 2008

In this paper a special class of quadratic functions, the so called half-products are considered. It is shown that while the minimization over the set of binary n-vectors for half-products is NP-complete, an ε-approximating solution can be found in polynomial time for any ε > 0.
Qualitative Sensitivity Analysis in Monotropic Programming
Authors: Gautier Antoine , Granot Frieda , Zheng Harry
Published: October 2008

Optimal selections are parameter-dependent optimal solutions of parametric optimization problems whose properties can be used in sensitivity analysis. Here we present a qualitative theory of sensitivity analysis for linearly-constrained convex separable (i.e., monotropic) parametric optimization problems. Three qualitative sensitivity analysis results previously derived for network flows are extended to monotropic problems: The Ripple and Smoothing Theorems give upper bounds on the magnitude of optimal-variable variations as a function of variations in the problem parameter(s), the theory of substitutes and complements provides necessary and sufficient conditions for optimal-variable changes to consistently have the same (or the opposite) sign(s) in two given variables, and the Monotonicity Theorem links changes in the value of the parameters to changes in optimal decision variables. We introduce a class of optimal selections for which these results hold, thereby answering a long-standing question due to Granot and Veinott (1985) with a simple and elegant method. Although a number of results are known to depend on the resolution of NP-complete problems, easily computable nonnetwork classes of monotropic problems such as unimodular systems of constraints emerge in the light of the present approach.
Robust Convex Optimization
Authors: Ben-Tal A. , Nemirovski A.
Published: October 2008

We study convex optimization problems for which the data is not specified exactly and it is only known to belong to a given uncertainty set U, yet the constraints must hold for all possible values of the data from U. The ensuing optimization problem is called robust optimization. In this paper we lay the foundation of robust convex optimization. In the main part of the paper we show that if U is an ellipsoidal uncertainty set, then for some of the most important generic convex optimization problems (linear programming, quadratically constrained programming, semidefinite programming and others) the corresponding robust convex program is either exactly, or approximately, a tractable problem which lends itself to efficient algorithms such as polynomial time interior point methods.
The Geometry of Fractional Stable Matchings and Its Applications
Authors: Teo Chung-Piaw , Sethuraman Jay
Published: October 2008

We study the classical stable marriage and stable roommates problems using a polyhedral approach. We propose a new LP formulation for the stable roommates problem, which has a feasible solution if and only if the underlying roommates problem has a stable matching. Furthermore, for certain special weight functions on the edges, we construct a 2-approximation algorithm for the optimal stable roommates problem. Our technique exploits features of the geometry of fractional solutions of this formulation. For the stable marriage problem, we show that a related geometry allows us to express any fractional solution in the stable marriage polytope as a convex combination of stable marriage solutions. This also leads to a genuinely simple proof of the integrality of the stable marriage polytope.
Single-Machine Scheduling of Unit-Time Jobs with Earliness and Tardiness Penalties
Authors: Verma Sushil , Dessouky Maged
Published: October 2008

The problem of determining a schedule of jobs with unit-time lengths on a single machine that minimizes the total weighted earliness and tardiness penalties with respect to arbitrary rational due-dates is formulated as an integer programming problem. We show that if the penalties meet a certain criterion, called the Dominance Condition, then there exists an extremal optimal solution to the LP-relaxation that is integral, leading to a polynomial-time solution procedure. The general weighted symmetric penalty structure is one cost structure that satisfies the Dominance Condition; we point out other commonly found penalty structures that also fall into this category.
The Cost of Achieving the Best Portfolio in Hindsight
Authors: Ordentlich Erik , Cover Thomas M.
Published: October 2008

For a market with m assets consider the minimum, over all possible sequences of asset prices through time n, of the ratio of the final wealth of a nonanticipating investment strategy to the wealth obtained by the best constant rebalanced portfolio computed in hindsight for that price sequence. We show that the maximum value of this ratio over all nonanticipating investment strategies is Vn = [∑ 2−nH(n_1/n,…,n_m/n)(n!/(n1! … nm!))]−1, where H(·) is the Shannon entropy, and we specify a strategy achieving it. The optimal ratio Vn is shown to decrease only polynomially in n, indicating that the rate of return of the optimal strategy converges uniformly to that of the best constant rebalanced portfolio determined with full hindsight. We also relate this result to the pricing of a new derivative security which might be called the hindsight allocation option.
On Computing the Nucleolus of a Balanced Connected Game
Authors: Solymosi Tamás , Aarts Harry , Driessen Theo
Published: October 2008

The question of “fairly” allocating costs or cost-savings among the participants of a joint enterprise is frequently answered by finding the nucleolus of a related cooperative game. In connection with various routing, sequencing and scheduling situations, connected games often arise. Their common feature is that all the essential coalitions (whose breaking up into subcoalitions is disadvantageous for its members) are connected with respect to a fixed order of the players (any player between two members of a coalition is also a member of the coalition). In the literature, several special classes of connected games are discussed that are shown to be balanced.

In this paper, an algorithm is presented that computes the nucleolus of a general n-person balanced connected game. The input is the array of the explicitly given values of the n(n + 1)/2 connected coalitions. The algorithm generates a sequence of at most n(n − 1)/2 payoff vectors starting from a special vertex of the nonempty core and ending in the nucleolus. By exploiting the special structure of connected games, the initial as well as the subsequent payoff vectors are obtained by evaluating some simple recursive formulas. It is shown that the algorithm requires at most O(n4) time and O(n2) space. A 5-person illustrative example is also given.
On a Representation of the Matching Polytope Via Semidefinite Liftings
Authors: Stephen Tamon , Tunçel Levent
Published: October 2008

We consider the relaxation of the matching polytope defined by the non-negativity and degree constraints. We prove that given an undirected graph on n nodes and the corresponding relaxation of the matching polytope, ⌊n/2⌋ iterations of the Lovász-Schrijver semidefinite lifting procedure are needed to obtain the matching polytope, in the worst case. We show that ⌊n/2⌋ iterations of the procedure always suffice.
Solutions to Affine Generalized Equations Using Proximal Mappings
Authors: Billups Stephen C. , Ferris Michael C.
Published: October 2008

The normal map has proven to be a powerful tool for solving generalized equations of the form: find z ∈ C, with 0 ∈ F(z) + N c (z), where C is a convex set and N c (z) is the normal cone to C at z. In this paper, we use the T-map, a generalization of the normal map, to solve equations of the more general form: find z ∈ dom(T), with 0 ∈ F(z) + T(z), where T is a maximal monotone multifunction. We present a path-following algorithm that determines zeros of coherently oriented piecewise-affine functions, and we use this algorithm, together with the T-map, to solve the generalized equation for affine, coherently oriented functions F, and polyhedral multifunctions T. The path-following algorithm we develop here extends the piecewise-linear homotopy framework of Eaves to the case where a representation of a subdivided manifold is unknown.
The Efficiency of Ballstep Subgradient Level Methods for Convex Optimization
Authors: Kiwiel Krzysztof C. , Larsson Torbjörn , Lindberg P. O.
Published: October 2008

We study subgradient methods for convex optimization that use projections onto successive approximations of level sets of the objective corresponding to estimates of the optimal value. We establish convergence and efficiency estimates for simple ballstep level controls without requiring that the feasible set be compact. Our framework may handle accelerations based on “cheap” projections, surrogate constraints, and conjugate subgradient techniques.
Erratum: The Travelling Salesman and the PQ-Tree
Authors: Burkard Rainer E. , Deĭneko Vladimir G. , Woeginger Gerhard J.
Published: October 2008

Let D=(dij) be the n×n distance matrix of a set of n cities {1,2,…,n}, and let T be a PQ-tree with node degree bounded by d that represents a set Π(T) of permutations over {1,2,…,n}. We show how to compute for D in O(2dn3) time the shortest travelling salesman tour contained in Π(T). Our algorithm may be interpreted as a common generalization of the well-known Held and Karp dynamic programming algorithm for the TSP and of the dynamic programming algorithm for finding the shortest pyramidal TSP tour.

A consequence of our result is that the shortcutting phase of the “twice around the tree” heuristic for the Euclidean TSP can be optimally implemented in polynomial time. This contradicts a statement of Papadimitriou and Vazirani as published in 1984.
Small Min-Cut Polyhedra
Authors: Alevras Dimitris
Published: October 2008

We study small min-cut polyhedra for directed and undirected complete graphs. We give the ideal descriptions of the polyhedra for undirected graphs with up to seven nodes and for directed graphs with up to five nodes, and generalize the inequalities for complete graphs with arbitrary number of nodes. The facial structure of the polyhedra turns out to be unexpectedly rich.
Superlinear Convergence of an Algorithm for Monotone Linear Complementarity Problems, When No Strictly Complementary Solution Exists
Authors: Sturm Jos F.
Published: October 2008

A new predictor-corrector interior point algorithm for solving monotone linear complementarity problems (LCP) is proposed, and it is shown to be superlinearly convergent with at least order 1.5, even if the LCP has no strictly complementary solution. Unlike the algorithm of Mizuno (1996), the fast local convergence is attained without any need for estimating the optimal partition. In the special case that a strictly complementary solution does exist, the order of convergence becomes quadratic. The proof relies on an investigation of the asymptotic behavior of first and second order derivatives that are associated with trajectories of weighted centers for monotone LCPs. The results of this investigation are also used to study convergence and error bounds of three Tapia-type indicators.
Random Sampling in Cut, Flow, and Network Design Problems
Authors: Karger David R.
Published: October 2008

We use random sampling as a tool for solving undirected graph problems. We show that the sparse graph, or skeleton, that arises when we randomly sample a graph's edges will accurately approximate the value of all cuts in the original graph with high probability. This makes sampling effective for problems involving cuts in graphs.

We present fast randomized (Monte Carlo and Las Vegas) algorithms for approximating and exactly finding minimum cuts and maximum flows in unweighted, undirected graphs. Our cut-approximation algorithms extend unchanged to weighted graphs while our weighted-graph flow algorithms are somewhat slower. Our approach gives a general paradigm with potential applications to any packing problem. It has since been used in a near-linear time algorithm for finding minimum cuts, as well as faster cut and flow algorithms.

Our sampling theorems also yield faster algorithms for several other cut-based problems, including approximating the best balanced cut of a graph, finding a k-connected orientation of a 2k-connected graph, and finding integral multicommodity flows in graphs with a great deal of excess capacity. Our methods also improve the efficiency of some parallel cut and flow algorithms.

Our methods also apply to the network design problem, where we wish to build a network satisfying certain connectivity requirements between vertices. We can purchase edges of various costs and wish to satisfy the requirements at minimum total cost. Since our sampling theorems apply even when the sampling probabilities are different for different edges, we can apply randomized rounding to solve network design problems. This gives approximation algorithms that guarantee much better approximations than previous algorithms whenever the minimum connectivity requirement is large. As a particular example, we improve the best approximation bound for the minimum k-connected subgraph problem from 1.85 to 1 + O(√(log n)/k).
On the Epiconvergence of Stochastic Optimization Problems
Authors: Zervos Mihail
Published: October 2008

The problem of strong consistency of sequences of optimal solutions to stochastic optimization problems is considered. This problem is related to a large number of applications including Bayesian decision problems and Monte Carlo simulations, as well as a number of statistical methodologies such as maximum likelihood estimation. The theory of epiconvergence being a framework within which such results can be established, the epiconvergence of the performance criteria of a sequence of stochastic optimization problems is proved under simple weak assumptions.
A Sharp Upper Bound for the Expected Number of Shadow Vertices in LP-Polyhedra Under Orthogonal Projection on Two-Dimensional Planes
Authors: Borgwardt Karl Heinz
Published: October 2008

Consider a set {a 1, …, am , u, v} ⊂ ℝ n satisfying a mild nondegeneracy condition. When the polyhedron X = {x ∣ a 1 T x ≤ 1, …, am T x ≤ 1} ⊂ ℝ n is orthogonally projected on the two-dimensional plane lin(u, v), then some of its vertices may be mapped on vertices of the two-dimensional image of X. These vertices of X will be called shadow vertices under that projection. Their number will be denoted by S.

This figure S has an outstanding relevance for the complexity of a special Simplex-Method, the dimension-by-dimension method, for solving LPs of the type

maximize  vTx

 s.t. a 1 Tx ≤ 1, …, am Tx ≤ 1 where x, v, a 1, …, am ∈ ℝ n and m ≥ n.

This method applies the “shadow vertex algorithm” in n − 1 stages of increasing dimension, by constructing a Simplex-Path that visits only shadow vertices. In each stage specific versions of the vectors u and v are used to define the projection plane and to control the application of the “shadow vertex algorithm.” So S delivers an upper bound for the length of such a path in one stage.

We want to study the average-case complexity of these algorithms and are therefore interested in Em,n (S), the expected value of S. For that purpose we assume a distribution of the linear programming problems corresponding to the rotation symmetry model (RSM):

The vectors a 1, …, am , u, v are distributed on ℝ n \{0} independently, identically and symmetrically under rotations.

In this paper we improve the upper bounds for Em,n (S) from our polynomiality-proofs of 1982 and 1987. There we had found an upper bound of m 1/( n −1) · n 3 · Const., valid for all RSM-distributions and all pairs (m ≥ n).

Based on a refined evaluation technique for space-angles, on a reorganization and on substantial modifications of the old proof, we are now able to confirm a bound

Em,n (S) ≤ m 1/( n −1) · n 2 · Const. for all pairs (m,n) with m ≥ n.

This result had been desired since 1982, because then a bound m 1/( n −1) · n 2 · Const. had been derived exclusively for the situation, where n is fixed and m tends to infinity. All the time the question had been open, whether the asymptotical behaviour would be better than the behaviour in moderate dimensions, or whether the bound for the moderate case was crude.

In addition, we know—from an asymptotic analysis in 1987—that for a special RSM-distribution, namely the uniform distribution on the unit sphere, there is a lower bound for Em,n (S) of type m 1/( n −1) · n 2 · Const. The combination of this result and the new upper bound shows that the new bound is sharp.
Asymmetric Rendezvous on the Line Is a Double Linear Search Problem
Authors: Alpern Steve , Beck Anatole
Published: October 2008

We apply a new method of analysis to the asymmetric rendezvous search problem on the line (ARSPL). This problem, previously studied in a paper of Alpern and Gal (1995), asks how two blind, speed one players placed a distance d apart on the line, can find each other in minimum expected time. The distance d is drawn from a known cumulative probability distribution G, and the players are faced in random directions.

We show that the ARSPL is strategically equivalent to a new problem we call the double linear search problem (DLSP), where an object is placed equiprobably on one of two lines, and equiprobably at positions ±d. A searcher is placed at the origin of each of these lines. The two searchers move with a combined speed of one, to minimize the expected time before one of them finds the object.

Using results from a concurrent paper of the first author and J. V. Howard (1998), we solve the DLSP (and hence the ARSPL) for the case where G is convex on its support, and show that the solution is that conjectured in a paper of Baston and Gal (1998).
Interior Proximal and Multiplier Methods Based on Second Order Homogeneous Kernels
Authors: Auslender Alfred , Teboulle Marc , Ben-Tiba Sami
Published: October 2008

We study a class of interior proximal algorithms and nonquadratic multiplier methods for solving convex programs, where the usual proximal quadratic term is replaced by an homogeneous functional of order two, defined in terms of a convex function. We prove, under mild assumptions, several new convergence results in both the primal and dual framework allowing also for approximate minimization. In particular, we introduce a new class of interior proximal methods which is globally convergent and allows for generating C ∞ multiplier methods with bounded Hessians which exhibit strong convergence properties. We also consider linearly constrained convex problems and establish global quadratic convergence rates results for linear programs. We then study in detail a particular realization of these algorithms, leading to a new class of logarithmic-quadratic interior point algorithms which are shown to enjoy several attractive properties for solving constrained convex optimization problems.
Decision Making with Monotone Lower Probabilities of Infinite Order
Authors: Philippe Fabrice , Debs Gabriel , Jaffray Jean-Yves
Published: October 2008

Properties of convex and monotone capacities of infinite order in Polish spaces are studied and used to justify the representation of certain situations of imprecise risk (imprecisely known probabilities) by lower probabilities, which are monotone of infinite order. Decision making with imprecise risk is then modeled, and linear utility theory is shown to be generalizable to the case of imprecise risk.
Repeated Games with Endogenous Choice of Information Mechanisms
Authors: Flesch János , Perea Y. Monsuwé Andres
Published: October 2008

We consider two-player repeated games with nonobservable actions (cf. Lehrer 1989). An information mechanism for a player is a function which assigns a private signal to every action-pair of the one-shot game. In this paper, we extend the model to a situation in which both players can buy an information mechanism before playing the repeated game. Within this model, we provide a characterization of the lower equilibrium payoffs in terms of the one-shot game for the case that both players choose a nontrivial information mechanism with probability one. Moreover, we construct a lower equilibrium in a repeated game in which one of the players strictly randomizes between information mechanisms. It is shown that the corresponding payoffs cannot be induced by a lower equilibrium in which players choose a particular information mechanism with probability one.
Generalized “Big-Match”
Authors: Coulomb J. M.
Published: October 2008

We define a specific class of zero-sum stochastic games with signals which are a generalization of the “Big-Match” game of Blackwell and Ferguson. We show the existence of the max min.
Interlacing Eigenvalues in Time Reversible Markov Chains
Authors: Brown Mark
Published: October 2008

For irreducible, reversible, finite state chains we observe that two sets of eigenvalues related to the transition rate matrix Q, (λ0, …, λ m ) and (γ1, …, γ m ), are interlaced so that λ0 < γ1 < λ1 < ⋯ < γ m < λ m . Many quantities associated with ℒπ TA , the distribution of the first passage time to A starting in steady state, can be simply expressed in terms of these eigenvalues, and the interlacing property can be exploited to obtain approximations. There is a close connection between interlacing eigenvalues and completely monotone distributions, as well as a representation for finite mixtures of exponential distributions, which follow from this observation.
Spatial Queueing Processes
Authors: Huang Xiaotao , Serfozo Richard F.
Published: October 2008

This study introduces a spatial queueing model for stochastic service systems in which customers or units move about and receive services in a region or a general space. The state of the system at any time is a point process that describes the numbers of units in subsets of the space, and the point process evolves over time as a Markov process. The system may be closed or open with a finite or unlimited capacity, and there may be multiple types of customers.

The main result is a closed form expression for the stationary distribution of a spatial queueing process. Sufficient conditions are given for the process to be ergodic. Further results include formulas for throughputs, Little laws for average waiting times in sectors of the space, and necessary and sufficient conditions for various flows in open systems to be Poisson processes in time and space. Examples are given of systems with sector-dependent service rates, local-regional service rates, and multiclass customers. A large family of spatial systems are multi-class queueing networks in which the customer classes are nondiscrete marks or quantities (e.g., resources for services, temperature, physical characteristics) that affect services and routings.
Markov Strategies in Dynamic Programming
Authors: Van Hee K. M.
Published: October 2008

It is shown that the supremum of the expected total return over the Markov strategies equals the supremum over all strategies. The model assumptions are: the state space is countable, the action space is measurable and the supremum of the expected total of the positive rewards over the Markov strategies is finite.
A Characterization of the Rau Class of Sequential Problems
Authors: Kadane Joseph B.
Published: October 2008

Rau (Rau, J. G. 1971. Minimizing a function of permutations of n integers. Oper. Res. 19 237–240.) presents a class of sequential problems including two important special cases from the search literature. Rau's class is presented there in terms of conditions that certain functions must satisfy. Here those conditions are reformulated to show what Rau's restrictions imply. A subclass of Rau's class is discussed that contains both of the important special cases, and which was used for further analysis in the paper of Kadane and Simon (Kadane, J. B., H. A. Simon. 1977. Optimal strategies for a class of constrained sequential problems. Ann. Statist. 5 237–255.).
The Recurrence Classification of Risk and Storage Processes
Authors: Harrison J. Michael , Resnick Sidney I.
Published: October 2008

Let X = {X(t), t ≥ 0} be a Markov storage process with compound Poisson input A = {A(t), t ≥ 0} and general release rule r(·). In a previous paper, a necessary and sufficient condition for the positive recurrence of X was obtained, and its stationary distribution was computed. Here we complete the recurrence classification of X, determining the conditions for null recurrence and transience.

Closely related to X is a Markov process X0 = {X0(t), t ≥ 0}. Its paths are absolutely continuous and increasing between downward jumps, the instantaneous rate of increase at time t being r(X0(t)). The jumps are generated by A but are truncated as necessary to keep X nonnegative. It is shown that X0 is positive recurrent iff X is transient, null recurrent iff X is null recurrent, and transient iff X is positive recurrent. Furthermore, in the case where X0 is transient, the probability that X0 ever hits zero (viewed as a function of the initial state) has the same density as the stationary distribution of X. A similar duality between the two processes is found in the case where X0 is positive recurrent.
On the Jacobian of a Function at a Zero Computed by a Fixed Point Algorithm
Authors: Todd Michael J.
Published: October 2008

Eaves and Scarf, and independently Todd, proved that the determinant of the Jacobian of a function at a zero computed by a fixed-point algorithm was zero or had the same sign as that of the artificial function used to start the algorithm. Here we show that any matrix satisfying this sign property can be realized as the Jacobian of a function at such a computed zero.
Some Basis Theorems for Integral Monoids
Authors: Jeroslow Robert G.
Published: October 2008

We consider sets of integer vectors containing the zero vector and closed under addition, the integral monoids, and provide conditions under which they contain a finite subset of integer vectors which generate the entire monoid as nonnegative integer combinations. The paper concludes with some applications to the theory of integer programming.
Conjugate Gradient Methods with Inexact Searches
Authors: Shanno David F.
Published: October 2008

Conjugate gradient methods are iterative methods for finding the minimizer of a scalar function f(x) of a vector variable x which do not update an approximation to the inverse Hessian matrix. This paper examines the effects of inexact linear searches on the methods and shows how the traditional Fletcher-Reeves and Polak-Ribiere algorithm may be modified in a form discovered by Perry to a sequence which can be interpreted as a memorytess BFGS algorithm. This algorithm may then be scaled optimally in the sense of Oren and Spedicalo. This scaling can be combined with Beale restarts and Powell's restart criterion. Computational results will show that this new method substantially outperforms known conjugate gradient methods on a wide class of problems.
Attainable Sets of Quasiconcave Markets, II: Convexifiable Sets
Authors: Weber Robert James
Published: October 2008

A set is convexifiabte if there exists a strictly increasing, continuous rescaling of the coordinate axes which makes the set convex. Several classes of sets are investigated with regard to this property. It is shown that every convexifiable compactly generated set is the attainable set of a market in which the traders have quasiconcave utility functions.
Threat Equilibria and Fair Settlements in Cooperative Games
Authors: Myerson Roger B.
Published: October 2008

The role of threats is studied in cooperative normal form games. A threats-game is constructed, in which every set of players selects a joint threat strategy and then a settlement function determines the final outcome. Threat equilibria and cooperative solutions are defined for any settlement function. Two axioms are introduced which determine a unique settlement function for games with transferable utility. This settlement function is closely related to the Shapley value, and has attractive Pareto-optimality and individual-rationality properties. A simple oligopoly problem is studied to illustrate these ideas.
Values of Large Games II: Oceanic Games
Authors: Milnor J. W. , Shapley L. S.
Published: October 2008

A value theory is developed for voting games in which a sizable fraction or the total vote is controlled by a few major players and the rest is distributed among a continuous infinity of individually insignificant minor players. The latter are referred to collectively as an “ocean,” to suggest the total lack of order or cohesion that is assumed.
Digraph Models of Bard-Type Algorithms for the Linear Complementarity Problem
Authors: Stickney Alan , Watson Layne
Published: October 2008

For M ∈ En×n and q ∈ En, the linear complementarity problem is to find vectors w, z ∈ En such that w − Mz = q, w ≥ 0, z ≥ 0, wtz = 0. A family of algorithms based on complementary pivoting for solving this problem is modelled by digraphs. These digraphs show that such algorithms can cycle even for symmetric, positive deFinite M, and provide some insight into the algorithms' behavior. For a P-matrix M, it is proved that if the solution to the complementarity problem can be obtained by k principal pivots, then it can be obtained by k Bard-type pivots. Furthermore, the digraphs provide simple geometric proofs of some of Murty's algebraic results. The digraphs, apart from their use as models, also raise some interesting graph-theoretic questions.
Overtaking Optimality for Markov Decision Chains
Authors: Denardo Eric V. , Rothblum Uriel G.
Published: October 2008

In a finite Markov decision chain, let V(n, Π)i denote the expectation of the income earned for starting at state i and following (stationary or nonstationary) policy Π for n epochs. Call policy Π overtaking optimal if lim infn→∞ {V(n, Π)i − V(n, Λ)i} ≥ 0 for every policy A and every state i. This paper provides conditions under which a certain stationary policy is overtaking optimal. Tests for these conditions are provided. These conditions hold, for instance, when Blackwell's (Blackwell, D. 1962. Discrete dynamic programming. Ann. Math. Statist. 33 719–726.) policy iteration routine terminates unambiguously, without ties, with a single policy whose transition matrix is not cyclic.
Reneging Phenomena in Single Channel Queues
Authors: Stanford Robert E.
Published: October 2008

We consider a GI/G/1 queueing system where the nth arrival may renege if his service does not commence before an elapsed random time Zn. Results for the general case include relations analogous to Little's formula L = λW, an expression for the average fraction of customers who renege from the system, expressions for the waiting time distribution for all arrivals to the system, the waiting time distribution for arrivals who reach the server, the distribution for virtual waiting time in the queue, and the distribution of the steady-state number of customers in the system and the number of customers left in the system by a completed service. These expressions are written in terms of the distribution of the work seen by an arbitrary arrival to the system, and an integral equation for this distribution is given along with necessary and sufficient conditions for existence of the distribution. Solutions to the integral equation are found for a number of forms for customer interarrival, service, and reneging distributions, and we show how the previous results on the subject of queueing with reneging follow as special cases of our approach. Some past and potential applications of queues with reneging are also discussed.
Expected Utility in Two-Person Games
Authors: Zachow Ernst-Wilhelm
Published: October 2008

Let P and Q be nonempty families of probability measures on the sets X and Y respectively of pure strategies which may be defined on different σ-algebras of subsets of X and Y respectively. For each q ∈ Q let (⊲, q) be a preference relation on P and for each p ∈ P let (p, ⊲) be a preference relation on Q. Necessary and sufficient conditions are given for the existence of a two-person zero-sum game (X, Y; a) such that (P, Q; A). A(p, q) = ∬a(x, y)dp(x)dq(y), is a randomization of (X, Y; a) which represents the preferences in the following sense: [Formula: see text] [Formula: see text] This result is applied to obtain an axiomatization of expected utility for general two-person games in normal form.
Renewal Decision Problem-Random Horizon
Authors: Derman C. , Smith D. R.
Published: October 2008

A system must operate for T units of time. T is a random variable with known distribution function F. A certain component is essential for the system’s operation and when it fails must be replaced with a new component. There are n possible types of replacements. An unlimited supply of each type is assumed. A type i replacement costs ci (ci > 0) and functions independently of T for an exponentially distributed length of time with rate λi. The problem is to assign the replacements from among the various possible types so as to minimize the expected total cost of providing an operative component for the entire life of the system. The principal result of this paper, generalizing previous work where T was assumed to have a degenerate or truncated exponential distribution, is that if F is an increasing failure rate function (IFR) the optimal replacement policy has a simple intuitive interval structure. An algorithm for finding the optimal policy is indicated. Some results are obtained for the case where component life distributions are not exponential.
The Partition Value
Authors: Neyman Abraham , Tauman Yair
Published: October 2008

The partition value is a new approach to the value concept. It links together the asymptotic and the axiomatic approach. Using this approach we prove the existence of a continuous value on each of the following spaces: bv′NA, A, A * bv′NA, A * bv′NA * bv′NA and the space W spanned by those spaces and ASYMP.
The Principal Maxmin Matrix Transversal Strategy
Authors: Kevorkian Aram K.
Published: October 2008

Given a fully irreducible matrix Y, we present a new matrix transversal strategy for the finding of a permutation matrix Q such that the condition numbers of the leading block A and its Schur complement D − CA−1 B in a 2 × 2 block form of YQ are as small as possible with respect to the i∞-norm. Our notion of principal maxmin transversal of a matrix is a special case of an important combinatorial mathematics notion introduced by P. Hall more than 40 years ago.
Penalty Lagrangian Methods Via a Quasi-Newton Approach
Authors: Han Shih-Ping
Published: October 2008

For solving nonlinear programming problems we iteratively minimize the penalty Lagrangian developed by Hestenes, Powell, and Rockafellar with the multipliers estimated by solving nonnegatively constrained quadratic programming subproblems and a penalty parameter updated by a scheme due to Powell and Fletcher. To ensure fast convergence the matrices in the subproblems are required to be good approximations to the Hessian inverse of the penalty Lagrangian. We suggest some quasi-Newton updates such as the well-known BFGS update to construct these matrices. The resulting methods possess local and superlinear convergence properties and the penalty parameter remains bounded. Moreover, these results hold even if the penalty Lagrangian is not exactly minimized.
Geometric Properties of the Kernel, Nucleolus, and Related Solution Concepts
Authors: Maschler M. , Peleg B. , Shapley L. S.
Published: October 2008

Two solution concepts for cooperative games in characteristic-function form, the kernel and the nucleolus, are studied in their relationship to a number of other concepts, most notably the core. The unifying technical idea is to analyze the behavior of the strong ϵ-core as ϵ varies. One of the central results is that the portion of the prekernel that falls within the core, or any other strong ϵ-core, depends only on the latter's geometrical shape. The prekernel is closely related to the kernel and often coincides with it, but has a simpler definition and simpler analytic properties. A notion of “quasi-zero-monotonicity” is developed to aid in enlarging the class of games in which kernel considerations can be replaced by prekernel considerations. The nucleolus is approached through a new, geometrical definition, equivalent to Schmeidler's original definition but providing very elementary proofs of existence, unicity, and other properties. Finally, the intuitive interpretations of the two solution concepts are clarified: the kernel as a kind of multi-bilateral bargaining equilibrium without interpersonal utility comparisons, in which each pair of players bisects an interval which is either the battleground over which they can push each other aided by their best allies (if they are strong) or the no-man's-land that lies between them (if they are weak); the nucleolus as the result of an arbitrator's desire to minimize the dissatisfaction of the most dissatisfied coalition.
Closed Exponential Networks of Queues with Saturation: The Jackson-Type Stationary Distribution and Its Asymptotic Analysis
Authors: Pittel B.
Published: October 2008

Two models of a closed queueing network with saturation are proposed. Given that the “reversibility” condition holds in the first model, the stationary distribution is shown to be of product-form for either of them. Queueing networks with the space of admissible states generated by limited capacities of servers is the most important special variant of the general scheme. The asymptotic analysis of the stationary distribution in the case of a large number of customers is given and shows that a special nonlinear programming problem must be solved to obtain parameters of the limiting distribution. In particular, saturation probabilities are asymptotically expressed through the Lagrangian multipliers dual to corresponding linear restrictions of queue-sizes for servers with limited capacities.
Combinatorial Optimization: What is the State of the Art
Authors: Klee Victor
Published: October 2008

(Dedicated to E. J. McShane for his seventy-fifth birthday.) This survey attempts, without including many details of algorithms or of the underlying theory, to answer the following questions: What is combinatorial optimization? What are the landmarks of the theory? What are the most exciting recent advances? What are the most promising directions for research? What are the best sources of further information?
On the Relationship Between Conditions that Insure a PL Mapping is a Homeomorphism
Authors: Kojima M. , Saigal R.
Published: October 2008

In this note we consider two conditions which insure that a piecewise linear mapping is a homeomorphism. One of these is that the leading principal minors of certain matrices be positive, while the other is that all real eigenvalues be positive. We show that the latter condition is weaker than the former.
Rational Mixed-Integer and Polyhedral Union Minimization Models
Authors: Meyer R. R. , Thakkar M. V. , Hallman W. P.
Published: October 2008

The minimization model concept is defined, and its applications to nonlinear optimization are described. Necessary conditions and sufficient conditions are established for functions to have minimization models of certain types. These necessary conditions may also be thought of as properties of the optimal value functions of certain optimization problems subject to linear RHS perturbations.
Analysis of the Exceptional Queueing System by the Use of Regenerative Processes and Analytical Methods
Authors: Minh Do Le
Published: October 2008

This paper studies a queueing system in which the distributions of the first inter-arrival time and the first service time of each busy period are allowed to deviate from the usual GI/G/1 pattern. Under conditions insuring stability, we use analytical methods together with the property that the queueing process “starts anew” probabilistically whenever an arriving customer initiates a busy period to obtain various transient and stationary results for the system.
Strongly Regular Generalized Equations
Authors: Robinson Stephen M.
Published: October 2008

This paper considers generalized equations, which are convenient tools for formulating problems in complementarity and in mathematical programming, as well as variational inequalities. We introduce a regularity condition for such problems and, with its help, prove existence, uniqueness and Lipschitz continuity of solutions to generalized equations with parametric data. Applications to nonlinear programming and to other areas are discussed, and for important classes of such applications the regularity condition given here is shown to be in a certain sense the weakest possible condition under which the stated properties will hold.
A Note on Optimally Dissecting Simplices
Authors: Todd Michael J. , Acar Robert C.
Published: October 2008

We show that a certain dissection policy for n-simplices based on barycentric subdivision comes within a constant factor, independent of n, of the optimal rate of decrease in diameter. This result is of interest in constructing good triangulations for the homotopy algorithms that approximately compute fixed points.
A Survey and Comparison of Methods for Finding All Vertices of Convex Polyhedral Sets
Authors: Matheiss T. H. , Rubin David S.
Published: October 2008

This paper surveys the literature on methods for finding all vertices of convex polytopes, contrasting the main features of each method and providing computational results for representative methods.
Measure-Based Values of Market Games
Authors: Hart Sergiu
Published: October 2008

The idea of “marginal contribution” is best captured in the game theoretic concept of value. The relation between it and the usual economic equilibrium can be stated as the following Value Principle: in a perfectly competitive economy, every value allocation is competitive, and the two sets of allocations are identical if the economy is sufficiently differentiate. However, when modelling perfect competition by a nonatomic space of agents, the (asymptotic) value may fail to exist in the general (nondifferentiable) case. The purpose of this paper is to extend its existence, by adding a suitable requirement—namely, that it be “consistent” with the given “population measure.” Furthermore, the competitive price corresponding to the value allocation—for which we get an explicit formula—has interesting economic interpretations, as an “expected equilibrium price,” or as an “average best price,” both corresponding to a random sample (coalition) of agents.
Traversing Large Pieces of Linearity in Algorithms that Solve Equations by Following Piecewise-Linear Paths
Authors: Todd Michael J.
Published: October 2008

Simplicial or fixed-point algorithms trace piecewise-linear paths to approximate solutions of systems of nonlinear equations. We present improved methods that can traverse several simplices simultaneously. The technique applies particularly to functions with special structure, but also generally, since large pieces are always induced by the artifical affine function. The special structures considered are separability and partial separability.
Asymptotic Semivalues and a Short Proof of Kannai’s Theorem
Authors: Dubey Pradeep
Published: October 2008

Generalizations of the Shapley value, called semivalues, are introduced. We consider their asymptotic behavior for sequences of games that approach a nonatomic game, and show that limiting semivalues exist on pNA. In the process a short proof of Kannai’s asymptotic theorem for the Shapley value is also arrived at.