bluuebunny/crossref_metadata_2025 huggingface dataset:
Contraction Conditions for Average and α-Discount Optimality in Countable State Markov Games with Unbounded Rewards
Authors: Altman E. , Hordijk A. , Spieksma F. M.
Published: October 2008

The goal of this paper is to provide a theory of N-person Markov games with unbounded cost, for a countable state space and compact action spaces. We investigate both the finite and infinite horizon problems. For the latter, we consider the discounted cost as well as the expected average cost. We present conditions for the infinite horizon problems for which equilibrium policies exist for all players within the stationary policies, and show that the costs in equilibrium policies exist for all players within the stationary policies, and show that the costs in equilibrium satisfy the optimality equations. Similar results are obtained for the finite horizon costs, for which equilibrium policies are shown to exist for all players within the Markov policies. As special case of N-person games, we investigate the zero-sum (2 players) game, for which we establish the convergence of the value iteration algorithm. We conclude by studying an application of a zero-sum Markov game in a queueing model.
Numerical Analysis of American Option Pricing in a Jump-Diffusion Model
Authors: Zhang Xiao Lan
Published: October 2008

We discuss pricing formulae for American options in Merton's jump-diffusion model. With the help of variational inequalities, we derive some regularity properties of price functions. Using the finite difference method, a discretization scheme is presented and a convergence theorem for the first order derivatives is proved. Numerical methods and results are also discussed.
Continuous Characterizations of the Maximum Clique Problem
Authors: Gibbons Luana E. , Hearn Donald W. , Pardalos Panos M. , Ramana Motakuri V.
Published: October 2008

Given a graph G whose adjacency matrix is A, the Motzkin-Strauss formulation of the Maximum-Clique Problem is the quadratic program max{xT Ax ∣ xTe = 1, x ≥ 0}. It is well known that the global optimum value of this QP is (1 − 1/ω(G)), where ω(G) is the clique number of G. Here, we characterize the following properties pertaining to the above QP: (1) first order optimality, (2) second order optimality, (3) local optimality, (4) strict local optimality. These characterizations reveal interesting underlying discrete structures, and are polynomial time verifiable. A parametrization of the Motzkin-Strauss QP is then introduced and its properties are investigated. Finally, an extension of the Motzkin-Strauss formulation is provided for the weighted clique number of a graph.
How Does the Value Function of a Markov Decision Process Depend on the Transition Probabilities?
Authors: Müller Alfred
Published: October 2008

The present work deals with the comparison of (discrete time) Markov decision processes (MDPs), which differ only in their transition probabilities. We show that the optimal value function of an MDP is monotone with respect to appropriately defined stochastic order relations. We also find conditions for continuity with respect to suitable probability metrics. The results are applied to some well-known examples, including inventory control and optimal stopping.
Necessary Optimality Conditions for Optimization Problems with Variational Inequality Constraints
Authors: Ye J. J. , Ye X. Y.
Published: October 2008

In this paper we study optimization problems with variational inequality constraints in finite dimensional spaces. Kuhn-Tucker type necessary optimality conditions involving coderivatives are given under certain constraint qualifications including one that ensures nonexistence of non-trivial abnormal multipliers. The result is applied to bilevel programming problems to obtain Kuhn-Tucker type necessary optimality conditions. The Kuhn-Tucker type necessary optimality conditions are shown to be satisfied without any constraint qualification by the class of bilevel programming problems where the lower level is a parametric linear quadratic problem.
α-Covex Sets and Strong Quasiconvexity
Authors: Crouzeix J. P. , Ferland J. A. , Zălinescu C.
Published: October 2008

A major property of continuous strong convex functions is that they are inf-compact; hence, their minima are reached. In the past, several attempts have been made to extend strong convexity to generalized convexity, but they fail in the sense that they do not ensure inf-compactness.

In this paper, we introduce a concept of strong convexity on sets from which we deduce new concepts of strong quasiconvexity related to inf-compactness.
Faster Algorithms for the Generalized Network Flow Problem
Authors: Radzik Tomasz
Published: October 2008

We consider the generalized network flow problem. Each arc e in the network has a gain factor γ(e). If f(e) units of flow enter arc e, then f(e)γ(e) units arrive at the other end of e. The objective is to maximize the net flow into one specific node, the sink. The constraints are the conservation of flow at nodes and the capacities of arcs. We present a combinatorial algorithm which solves this problem in Õ(m2(m + n log log B)log B) time, where n is the number of nodes, m is the number of arcs, and B is the largest integer used to represent the gain factors, the capacities, and the initial supplies at the nodes. If m is O(n4/3−ε) and B is not extremely large, then our bound is better than the previous best upper bound for this problem. We also improve the best known upper bound for the approximate generalized flow problem by showing that a solution whose value is within a factor of 1 + ξ from the optimum can be computed in Õ(m(m + n log log B)log (1/ξ)) time plus Õ(mn2 log B) time for preprocessing.
On the Estimation of the Throughput for a Class of Stochastic Resources Sharing Systems
Authors: Brilman Matthieu , Vincent Jean-Marc
Published: October 2008

We present in this paper a stochastic model for a class of reservation systems, we define a performance parameter: γ. This parameter can be seen as the inverse of the asymptotic throughput of the system. We detail some of its elementary properties and show that it can be studied as a function of a graph, from a numerical point of view. We then show how it can be bounded by classical values associated to this graph, as the minimum degree, for instance. Finally, we discuss the interest of the bounds we obtain.
Perfect and Ideal 0, ±1 Matrices
Authors: Guenin Bertrand
Published: October 2008

A 0, ±1 matrix A is said to be perfect (resp. ideal) if the corresponding generalized packing (resp. covering) polytope is integral. Given a 0, ±1 matrix A, we construct a 0, 1 matrix that is perfect if and only if A is perfect. A similar result is obtained for the generalized covering problem. We also extend some known results on perfect 0, 1 matrices to the 0, ±1 case.
Existence and Discovery of Average Optimal Solutions in Deterministic Infinite Horizon Optimization
Authors: Schochetman Irwin E. , Smith Robert L.
Published: October 2008

We consider the problem of making a sequence of decisions, each chosen from a finite action set over an infinite horizon, so as to minimize its associated average cost. Both the feasibility and cost of a decision are allowed to depend upon all of the decisions made prior to that decision; moreover, time-varying costs and constraints are allowed. A feasible solution is said to be efficient if it reaches each of the states through which it passes at minimum cost. We show that efficient solutions exist and that, under a state reachability condition, efficient solutions are also average optimal. Exploiting the characterization of efficiency via a solution's short-run as opposed to long-run behavior, a forward algorithm is constructed which recursively discovers the first, second, and subsequent decisions of an efficient, and hence average optimal, infinite horizon solution.
A Homological Characterization of Q-Matrices
Authors: Naiman Daniel Q. , Stone Richard E.
Published: October 2008

A real square matrix M is said to be a Q-matrix if the linear complementarity problem (q, M) has a solution for every vector q. There is, as yet, no characterization of Q-matrices which makes it easy to determine whether or not a given matrix is Q. Ideas from topology, in particular degree theory, have previously been used to obtain sufficient conditions for when a matrix is Q. In this paper we will apply some other ideas from topology to give a homological characterization of Q-matrices. Continuing to borrow from topology, we define the nerve of a matrix which, along with our characterization, leads to an algorithm for checking whether or not a matrix is Q. This algorithm has smaller bounds on its worst-case time complexity than previous methods.
Geometric Convergence of Algorithms in Gambling Theory
Authors: Ramakrishnan S. , Sudderth W.
Published: October 2008

In the Dubins and Savage theory of gambling, backward induction provides an algorithm for calculating the optimal return when the gambling problem is leavable. A relatively new algorithm works for nonleavable problems. We show that these algorithms converge geometrically fast for finite gambling problems. Our argument also provides a much simpler proof of convergence for the nonleavable case.
Local Risk-Minimization Under Transaction Costs
Authors: Lamberton Damien , Pham Huyên , Schweizer Martin
Published: October 2008

We propose a new approach to the pricing and hedging of contingent claims under transaction costs in a general incomplete market in discrete time. Under the assumptions of a bounded mean-variance tradeoff, substantial risk and a nondegeneracy condition on the conditional variances of asset returns, we prove the existence of a locally risk-minimizing strategy inclusive of transaction costs for every square-integrable contingent claim. Then we show that local risk-minimization is robust under the inclusion of transaction costs: The preceding strategy which is locally risk-minimizing inclusive of transaction costs in a model with bid-ask spreads on the underlying asset is also locally risk-minimizing without transaction costs in a fictitious model which is frictionless and where the fictitious asset price lies between the bid and ask price processes of the original model. In particular, our results apply to any nondegenerate model with a finite state space if the transaction cost parameter is sufficiently small.
On Local Search for Weighted k-Set Packing
Authors: Arkin Esther M. , Hassin Refael
Published: October 2008

Given a collection of sets of cardinality at most k, with weights for each set, the maximum weighted packing problem is that of finding a collection of disjoint sets of maximum total weight. We study the worst case behavior of the t-local search heuristic for this problem proving a tight bound of k − 1 + 1/t. As a consequence, for any given r < 1/(k − 1) we can compute in polynomial time a solution whose weight is at least r times the optimal.
A Submodular Optimization Problem with Side Constraints
Authors: Hartvigsen David
Published: October 2008

In this paper we consider the general problem of optimizing over the intersection of a submodular base polyhedron and an affine space. An example is the following flow problem defined on a capacitated network: We wish to send a commodity from locations in a producing country to locations in a number of client countries so as to simultaneously maximize profits and send to each client country a prescribed proportion of the total sent. We present an algorithm for the general problem and analyze its complexity.
Primal-Dual Symmetry and Scale Invariance of Interior-Point Algorithms for Convex Optimization
Authors: Tunçel Levent
Published: October 2008

We present a definition of symmetric primal-dual algorithms for convex optimization problems expressed in the conic form. After describing a generalization of the v-space approach for such optimization problems, we show that a symmetric v-space approach can be developed for a convex optimization problem in the conic form if and only if the underlying cone is homogeneous and self-dual. We provide an alternative definition of self-scaled barriers and then conclude with a discussion of the scalings of the variables which keep the underlying convex cone invariant.
Structural and Stability Properties ofP0Nonlinear Complementarity Problems
Authors: Facchinei Francisco
Published: October 2008

We consider P0nonlinear complementarity problems and study the connectedness and stability of the solutions by applying degree theory and the Mountain Pass Theorem to a smooth reformulation of the complementarity problem. We show that the solution set is connected and bounded if a bounded isolated component of the solution set exists and that a solution is locally unique if and only if it is globally unique. Furthermore, we prove that a solution is stable in Ha's sense if and only if it is globally unique, while the complementarity problem is stable if and only if the solution set is bounded.
Erratum: Probabilistic Models for Linear Programming
Authors: Todd M. J.
Published: October 2008

In the paper “Probabilistic models for linear programming,” published in Mathematics of Operations Research, Vol. 16, No. 4, pp. 671–693 , the author proposed various models for generating random linear programming problems and investigated several properties of these models, including the probability that the feasible region is bounded, the distribution of the distance from a particular interior point to each constraint hyperplane, and some properties of the vertices of the feasible region. Unfortunately, one of the results about these vertices is incorrect, and this affects some of the corollaries. Here it is described what is invalid, and explained where the difficulty arises in the proof.
Discounted Stochastic Games
Authors: Solan Eilon
Published: October 2008

We give an alternative proof to a result of Mertens and Parthasarathy, stating that every n-player discounted stochastic game with general setup, and with a norm-continuous transition, has a subgame perfect equilibrium.
Erratum: Critical Cutsets of Graphs and Canonical Facets of Set Packing Polytopes (Mathematics of Operations Research, Vol. 2, 1977, 15–19)
Authors: Balas Egon , Zemel Eitan
Published: October 2008

Theorem 2, published in the paper “Critical cutsets of graphs and canonical facets of set packing polytopes,” (Mathematics of Operations Research, Vol. 2, No. 1, pp. 15–19 , 1977) as stated is false, the conditions given are not sufficient to define a facet of P(G). We are grateful to Sven de Vries for querying us about a flaw in our proof. A correction of condition (ii) of Theorem 2 is given.
Matrices with Identical Sets of Neighbors
Authors: Bárány Imre , Scarf Herbert
Published: October 2008

Given a generic m by n matrix A, a lattice point h in ℤ n is a neighbor of the origin if the body {x: Ax ≤ b}, with bi = max{0, aih}, i = 1, …, m, contains no lattice point other than 0 and h. The set of neighbors, N(A), is finite and 0-symmetric. We show that if A′ is another matrix of the same size with the property that sign aih = sign ai ′h for every i and every h ∈ N(A), then A′ has precisely the same set of neighbors as A. The collection of such matrices is a polyhedral cone, described by a finite set of linear inequalities, each such inequality corresponding to a generator of one of the cones Ci = pos{h ∈ N(A): aih < 0}. Computational experience shows that Ci has “few” generators. We demonstrate this in the first nontrivial case n = 3, m = 4.
Approximation Algorithms for the Discrete Time-Cost Tradeoff Problem
Authors: Skutella Martin
Published: October 2008

Due to its obvious practical relevance, the Time-Cost Tradeoff Problem has attracted the attention of many researchers over the last forty years. While the Linear Time-Cost Tradeoff Problem can be solved in polynomial time, its discrete variant is known to be NP-hard. We present the first approximation algorithms for the Discrete Time-Cost Tradeoff Problem. Specifically, given a fixed budget we consider the problem of finding a shortest schedule for a project. We give an approximation algorithm with performance ratio 3/2 for the class of projects where all feasible durations of activities are either 0, 1, or 2. We extend our result by giving approximation algorithms with performance guarantee O(log l), where l is the ratio of the maximum duration of any activity to the minimum nonzero duration of any activity. Finally, we discuss bicriteria approximation algorithms which compute schedules for a given deadline or budget such that both project duration and cost are within a constant factor of the duration and cost of an optimum schedule for the given deadline or budget.
Positive Dependence Properties of Conditionally Independent Random Lifetimes
Authors: Shaked Moshe , Spizzichino Fabio
Published: October 2008

Conditions under which conditionally independent random variables are positive dependent are described in this paper. For example, it is shown that if the conditionally independent random variables increase in the hazard rate sense in the condition, then they are WBF (weakened by failures). It is also shown that if the conditionally independent random variables increase in the likelihood ratio sense in the condition, then they are MTP2 (multivariate totally positive of order 2). The results are given for the cases in which the condition is either a random variable or a random vector. Some applications in the areas of imperfect repair, budget allocation, random environments, and discrete-time filtering, illustrate the theory.
Separating Maximally Violated Comb Inequalities in Planar Graphs
Authors: Fleischer L. , Tardos É.
Published: October 2008

The Traveling Salesman Problem (TSP) is a benchmark problem in combinatorial optimization. It was one of the very first problems used for developing and testing approaches to solving large integer programs, including cutting plane algorithms and branch-and-cut algorithms. Much of the research in this area has been focused on finding new classes of facets for the TSP polytope, and much less attention has been paid to algorithms for separating from these classes of facets.

In this paper, we consider the problem of finding violated comb inequalities. If there are no violated subtour constraints in a fractional solution of the TSP, a comb inequality may not be violated by more than 1. Given a fractional solution in the subtour elimination polytope whose graph is planar, we either find a violated comb inequality or determine that there are no comb inequalities violated by 1. Our algorithm runs in O(n + MC(n)) time, where MC(n) is the time to compute a cactus representation of all minimum cuts of a weighted planar graph on n vertices.
M-Convex Function on Generalized Polymatroid
Authors: Murota Kazuo , Shioura Akiyoshi
Published: October 2008

The concept of M-convex function, introduced by Murota (1996), is a quantitative generalization of the set of integral points in an integral base polyhedron as well as an extension of valuated matroid of Dress and Wenzel (1990). In this paper, we extend this concept to functions on generalized polymatroids with a view to providing a unified framework for efficiently solvable nonlinear discrete optimization problems.
Processor Shadowing: Maximizing Expected Throughput in Fault-Tolerant Systems
Authors: Bruno J. L. , Coffman E. G. , Lagarias J. C. , Richardson T. J. , Shor P. W.
Published: October 2008

This paper studies parallel processing as a device for increasing fault tolerance. In the first of two basic models, a single job with a given running time is to be run on a finite set of processors; each processor is subject to failure but only while running a job. If a job is running on only one processor, and that processor fails, then the job must be restarted on another processor, assuming not all processors have already failed. To avoid such losses in accrued running time when at least two processors are available, it can be decided at any time to run the job synchronously on two processors in parallel, a replication technique we call shadowing. Clearly, shadowing has its own downside: while two processors are running, the failure rate is doubled. We show how to resolve this trade-off optimally; we devise a policy that schedules shadowing in such a way as to maximize the probability that the job finishes before all processors fail. We prove that the policy is of threshold type. That is, depending on the number of processors and the duration of the job, there is an optimal time to begin shadowing; once started, shadowing continues so long as neither processor fails and the job does not complete. We also show that the thresholds are monotone in the number of processors, i.e., if more processors are initially available, then shadowing should be started sooner.

In the second of our two models, we have the same set-up except that we have an unbounded number of jobs, each having the same running time, and the objective is to maximize the expected number of jobs completed before all processors fail. We show that the optimal policy is again of threshold type, but that the thresholds are, surprisingly, not monotone in the number of processors. The optimal thresholds have a curious oscillatory behavior that we study in detail.

Variants of the above problems are also analyzed using the same methods; several other variants are left as interesting open problems.
Transience Bounds for Long Walks
Authors: Hartmann Mark , Arguelles Cristina
Published: October 2008

Let G = (V, E) be a directed graph with rewards r e for e ∈ E. We show that if there exists an s, t-walk in G of length k > |V|2 then there exists a maximum reward s, t-walk of length k with at least k − |V|2 arcs from a cycle with maximal mean reward. If A is the reward-incidence matrix of G, then the maximum rewards of s, t-walks of length k can be determined by computing the k-fold matrix product A ⊗ k , where the operations “plus” and “times” are replaced by “max” and “plus” (denoted by ⊕ and ⊗). Max-algebra dynamic systems y(k) = y(k − 1) ⊗ A have been used to model certain transportation and automated manufacturing systems, and can be interpreted as deterministic dynamic programming recursions. If G is strongly connected, then y(k + d A ) = y(k) + d A λ*1 for all k ≥ K A , where λ* is the maximum cycle mean in G, and K A and d A are the max-algebra transient and period (cyclicity) of A. For given y(0), the transient τ and period γ of the system may satisfy τ < K A and γ < d A . We derive a tight bound on K A and give polynomial algorithms for computing K A , τ and γ, and for solving deterministic dynamic programming problems. We also give analogous results for walks of maximum β-discounted reward.
Global Convergence Analysis of the Generalized Newton and Gauss-Newton Methods of the Fischer-Burmeister Equation for the Complementarity Problem
Authors: Jiang Houyuan
Published: October 2008

The nonlinear complementarity problem has been converted into a system of nonsmooth equations by means of Fischer-Burmeister functional, which may be called the Fischer-Burmeister equation. The local superlinear convergence of the generalized Newton method applied to the Fischer-Burmeister equation has been established under certain regularity assumptions. In contrast to the damped Newton method for systems of smooth equations, global convergence of the damped generalized Newton method for systems of nonsmooth equations cannot be proved in general. In this paper, we show that the natural globalization of the Newton method for smooth equations can be extended to the Fischer-Burmeister equation without any hybrid strategy. Moreover, we are also able to demonstrate that the damped modified Gauss-Newton method can be extended to the Fischer-Burmeister equation. This shows that the elegant convergence analysis of the traditional Newton, damped Newton and damped Gauss-Newton methods can be naturally generalized to the Fischer-Burmeister equation.
“Cav u” and the Dual Game
Authors: De Meyer Bernard , Rosenberg Dinah
Published: October 2008

We give an alternative proof of a theorem of Aumann and Maschler that characterizes the limit of the values of finitely repeated games with lack of information on one side as the concavification of the value of the game where none of the players has any information. Our proof is based on Fenchel duality techniques.
Optimality Conditions for a Class of Mathematical Programs with Equilibrium Constraints
Authors: Outrata J. V.
Published: October 2008

The paper deals with mathematical programs, where parameter-dependent nonlinear complementarity problems arise as side constraints. Using the generalized differential calculus for nonsmooth and set-valued mappings due to B. Mordukhovich, we derive 1st-order necessary optimality conditions. The imposed constraint qualification is studied in detail and compared with other conditions arising in this context.
Modified Wilson's Method for Nonlinear Programs with Nonunique Multipliers
Authors: Fischer Andreas
Published: October 2008

This paper first investigates Newton-type methods for generalized equations with compact solution sets. The analysis of their local convergence behavior is based, besides other conditions, on the upper Lipschitz-continuity of the local solution set mapping of a simply perturbed generalized equation.

This approach is then applied to the KKT conditions of a nonlinear program with inequality constraints and leads to a modified version of the classical Wilson method. It is shown that the distances of the iterates to the set of KKT points converge q-quadratically to zero under conditions that do not imply a unique multiplier vector. Additionally to the Mangasarian-Fromovitz Constraint Qualification and to a Second-Order Sufficiency Condition the local minimizer is required to fulfill a Constant Rank Condition (weaker than the Constant Rank Constraint Qualification one of Janin) and a so-called Weak Complementarity Condition.
The Flatness Theorem for Nonsymmetric Convex Bodies via the Local Theory of Banach Spaces
Authors: Banaszczyk Wojciech , Litvak Alexander E. , Pajor Alain , Szarek Stanislaw J.
Published: October 2008

Let L be a lattice in ℝ n and K a convex body disjoint from L. The classical Flatness Theorem asserts that then w(K, L), the L-width of K, does not exceed some bound, depending only on the dimension n; this fact was later found relevant to questions in integer programming. Kannan and Lovász (1988) showed that under the above assumptions w(K, L) ≤ Cn 2, where C is a universal constant. Banaszczyk (1996) proved that w(K, L) ≤ Cn(1 + log n) if K has a centre of symmetry. In the present paper we show that w(K, L) ≤ Cn 3/2 for an arbitrary K. It is conjectured that the exponent 3/2 may be replaced by 1, perhaps at the cost of a logarithmic factor; we prove that for some naturally arising classes of bodies.
Algorithmic Aspects of the Core of Combinatorial Optimization Games
Authors: Deng Xiaotie , Ibaraki Toshihide , Nagamochi Hiroshi
Published: October 2008

We discuss an integer programming formulation for a class of cooperative games. We focus on algorithmic aspects of the core, one of the most important solution concepts in cooperative game theory. Central to our study is a simple (but very useful) observation that the core for this class is nonempty if and only if an associated linear program has an integer optimal solution. Based on this, we study the computational complexity and algorithms to answer important questions about the cores of various games on graphs, such as maximum flow, connectivity, maximum matching, minimum vertex cover, minimum edge cover, maximum independent set, and minimum coloring.
Two-Machine No-Wait Flow Shop Scheduling with Missing Operations
Authors: Glass C. A. , Gupta J. N. D. , Potts C. N.
Published: October 2008

This paper considers the no-wait scheduling of n jobs in a two-machine flow shop, where some jobs require processing on the first machine only. The objective is to minimize the maximum completion time, or makespan. In view of its NP-hardness, we propose and analyze heuristic algorithms. Our main result is an O(n log n)-time heuristic which generates a schedule with makespan no more than 4/3 times that of an optimal schedule. This heuristic solves optimally the subproblem involving the jobs with no missing operations, using, for example, the well-known algorithm of Gilmore and Gomory, and then uses a list scheduling procedure to insert the remaining jobs in the schedule. A new proof technique is employed in the worst-case analysis, which has potential application in a variety of bin packing and scheduling problems.
Values of Large Games, I: A Limit Theorem
Authors: Shapiro N. Z. , Shapley L. S.
Published: October 2008

This paper gives an analysis of what happens in a weighted majority game when a block of votes is broken up and distributed among a large number of players. It is shown that the value of the game to the other players converges to a limit as the size of the largest fragment tends to zero. An explicit expression is given for the limit.
A Least-Element Theory of Solving Linear Complementarity Problems as Linear Programs
Authors: Cottle Richard W. , Pang Jong-Shi
Published: October 2008

In a previous report (Cottle, R. W., J. S. Pang. 1978. On solving linear complementary problems as linear programs. Math. Programming Stud. 7 88–107.), the authors have established a least-element interpretation to Mangasarian's theory (Mangasarian, O. L. 1976. Linear complementarity problems solvable by a single linear program. Math. Programming 10 263–270; Mangasarian, O. L. 1975. Solution of linear complementarity problems by linear programming. In G. W. Watson, ed. Numerical Analysis, Dundée 1975. Lecture Notes in Mathematics, No. 506, Springer-Verlag, Berlin, 166–175.) of formulating some linear complementarity problems as linear programs. In the present report, we extend our previous analysis to a more general class of linear complementarity problems investigated in Mangasarian (Mangasarian, O. L. 1978. Characterization of linear complementarity problems as linear programs. Math. Programming Stud. 7 74–87.), Our purposes are (1) to demonstrate how solutions to these problems can be generated from least elements of polyhedral sets and (2) to investigate how these “least-element solutions” are related to the solutions obtained by the linear programming approach as proposed by Mangasarian.
Convex Operators and Supports
Authors: Brumelle S. L.
Published: October 2008

In this paper we show that if Z is a partially ordered linear space with the property that each set with an upper bound has a least upper bound, then any convex operator F from a linear space X into Z has a support at each x ∈ X (i.e., for each x ∈ X, there exists an affine operator A such that A(x) = F(x) and A(y) ≤ F(y) for each y ∈ X).

The results in this paper are actually in the context of a more general condition than convexity, called W-convexily. W-convexity is a pointwise property of an operator and is closely related to another generalization of convexity, called order-convexity, which was introduced by Ortega and Rheinboldt in 1967.
Approximation Algorithms for Certain Scheduling Problems
Authors: Ibarra Oscar H. , Kim Chul E.
Published: October 2008

A subset of a set of tasks ℱ is to be scheduled on a single processor. Associated with each task J time μ(J) and profit p(J). The tasks have precedence constraints in that a task cannot be scheduled until all of its predecessors have been scheduled. Approximation algorithms of polynomial time complexity are presented for the following problems:

MAXPROFIT problem. Given T, the available processor time, find a subset L of ℱ such that ∑L∈Lμ(J) ≤ T and ∑J∈LP(J) is maximal.

MINTIME problem. Given P, the minimum profit desired, find a subset L of ℱ such that ∑J∈LP(J) ≥ p and ∑J∈Lμ(J) is minimal.
Approximating Many Server Queues by Means of Single Server Queues
Authors: Arjas Elja , Lehtonen Tapani
Published: October 2008

Obtaining time dependent results for many server queues is, under general structural assumptions, a hard problem. This paper makes an attempt to approximate stochastically the behaviour of a general many server queue by using single server queues as stochastic bounds. We propose three alternative ways of constructing approximating single server queues. The first technique utilizes special classes of service time distributions (new better than used, new worse than used), the second is via dividing the service times by the number of servers, and the third is based on a grouping idea of the customers. The first and third techniques yield in fact two bounding queues each, one of which is faster and one slower than the original s-server queue.
Approximations of Dynamic Programs, I
Authors: Whitt Ward
Published: October 2008

A general procedure is presented for constructing and analyzing approximations of dynamic programming models. The models considered are the monotone contraction operator models of Denardo (Denardo, E. V. 1967. Contraction mappings in the theory underlying dynamic programming. SIAM Rev. 9 165–177.), which include Markov decision processes and stochastic games with a criterion of discounted present value over an infinite horizon plus many finite-stage dynamic programs. The approximations are typically achieved by replacing the original state and action spaces by subsets. Tight bounds are obtained for the distances between the optimal return function in the original model and (1) the extension of the optimal return function in the approximate model and (2) the return function associated with the extension of an optimal policy in the approximate model. Conditions are also given under which the sequence of bounds associated with a sequence of approximating models converges to zero.
Coherent Systems with Multi-State Components
Authors: Barlow Richard E. , Wu Alexander S.
Published: October 2008

The theory of binary coherent systems is generalized for multi-state components. The system state is defined to be the state of the “worst” component in the “best” min path, or equivalently, the state of the “best” component in the “worst” min cut. Many of the results for the binary case can be computed for multi-state systems using the binary structure and reliability function concepts. Monotonicity results are now valid with respect to stochastic ordering of component probability vectors.
A Theorem on Homotopy Paths
Authors: Garcia C. B. , Gould F. J.
Published: October 2008

We consider the set of points x ∈ Rn+1 satisfying H(x) = 0, where H: Rn+1 → Rn is a C1 function and 0 is a regular value. This set, H−1(0), is a C1 one-dimensional manifold, and each component can be described by a curve x(θ). In this note a theorem is proved which is directly related to and motivated by a result due to Eaves and Scarf on piecewise linear functions. This theorem relates the signs of the derivatives xt(θ) to the signs of the determinants of submatrices of the Jacobian matrix H′. Applications to solving nonlinear equations are given.
Semi-Regenerative Processes with Unbounded Rewards
Authors: Schellhaas Helmut
Published: October 2008

A semi-regenerative process (SRP) is combined with a reward structure such that the accumulated reward during [0, t] is the sum of a functional of the SRP and a functional of the embedded Markov renewal process (MRP). For the expected (discounted) return a Markov renewal equation (MRE) is given. The solution of the MRE is investigated using bounding functions in case the expected (discounted) return between two successive regeneration times of the MRP is not bounded as is the rule in many applications. Explicit limiting results for t → ∞ are given for the expected return in case of discounting and the return rate in case of no discounting.
On Piecewise Linear Approximations to Smooth Mappings
Authors: Saigal R.
Published: October 2008

Given a continuously differentiable mapping f from Rn into Rn, in this work we study piecewise linear approximations to it on certain subdivisions of Rn. It is shown that several properties of the subdivision are critical when the Jacobians of the pieces of linearity of the approximation are required to be close to the Jacobians of f. In addition, it is shown that even under arbitrary scaling of the triangulations used in fixed point algorithms, good approximations of the derivatives result.
Approximations of Dynamic Programs, II
Authors: Whitt Ward
Published: October 2008

This paper extends a procedure for approximating dynamic programs due to Fox (Fox, B. L. 1971. Finite-state approximations to denumerable-state dynamic programs. J. Math. Anal. Appl. 34 665–670.). Here, the monotone contraction operator model of Denardo (Denardo, E. V. 1967. Contraction mappings in the theory underlying dynamic programming. SIAM Rev. 9 165–177.) is approximated by replacing the state space with a subset and defining two approximate local income functions so that the two associated approximate optimal return functions serve as lower and upper bounds for the optimal return function in the original model. Conditions are also given implying convergence of a sequence of approximate optimal return functions to the optimal return function in the original model.
Mathematical Properties of the Banzhaf Power Index
Authors: Dubey Pradeep , Shapley Lloyd S.
Published: October 2008

The Banzhaf index of power in a voting situation depends on the number of ways in which each voter can effect a “swing” in the outcome. It is comparable—but not actually equivalent—to the better-known Shapley-Shubik index, which depends on the number of alignments or “orders of support” in which each voter is pivotal. This paper investigates some properties of the Banzhaf index, the main topics being its derivation from axioms and its behavior in weighted-voting models when the number of small voters tends to infinity. These matters have previously been studied from the Shapley-Shubik viewpoint, but the present work reveals some striking differences between the two indices. The paper also attempts to promote better communication and less duplication of mathematical effort by identifying and describing several other theories, formally equivalent to Banzhaf’s, that are found in fields ranging from sociology to electrical engineering. An extensive bibliography is provided.
A Greedy Heuristic for the Set-Covering Problem
Authors: Chvatal V.
Published: October 2008

Let A be a binary matrix of size m × n, let cT be a positive row vector of length n and let e be the column vector, all of whose m components are ones. The set-covering problem is to minimize cTx subject to Ax ≥ e and x binary. We compare the value of the objective function at a feasible solution found by a simple greedy heuristic to the true optimum. It turns out that the ratio between the two grows at most logarithmically in the largest column sum of A. When all the components of cT are the same, our result reduces to a theorem established previously by Johnson and Lovasz.
On Fulkerson's Conjecture About Consistent Labeling Processes
Authors: Megiddo Nimrod , Galil Zvi
Published: October 2008

Fulkerson conjectured that any consistent labeling process implies a polynomial time bound for the Ford-Fulkerson max-flow algorithm. The conjecture is disproved by means of a sequence of networks requiring an exponential number of augmentations, resulting from a consistent labeling process. On the other hand, it is shown that any consistent labeling process yields an algorithm which runs in time O[Min(V!, 3E)]. This result is stronger than A. Tucker's which states that consistency implies a finite number of augmentations.
Fast Approximation Algorithms for Knapsack Problems
Authors: Lawler Eugene L.
Published: October 2008

Fully polynomial approximation schemes for knapsack problems are presented. These algorithms are based on ideas of Ibarra and Kim, with modifications which yield better time and space bounds, and also tend to improve the practicality of the procedures. Among the principal improvements are the introduction of a more efficient method of scaling and the use of a median-finding routine to eliminate sorting. The 0-1 knapsack problem, for n items and accuracy ϵ > 0, is solved in (n log(1/ϵ) + 1/ϵ4) time and O(n + 1/ϵ3) space. The time bound is reduced to O(n + 1/ϵ3) for the “unbounded” knapsack problem. For the “subset-sum” problem, O(n + 1/ϵ3) time and O(n + 1/ϵ2) space, or O(n + (1/ϵ2)log(1/ϵ)) time and space, are achieved. The “multiple choice” problem, with m equivalence classes, is solved in O(n log n + mn/ϵ) time and O(n + m2/ϵ) space.
An Approach to Homotopy and Degree Theory
Authors: Garcia C. B. , Zangwill W. I.
Published: October 2008

Spawned by Scarf's pioneering work on the calculation of fixed points, an entire new field in mathematical programming has emerged. A wide array of problems that can be posed as fixed point problems, such as problems involving equilibria, games, systems of equations, global optimization, and structural mechanics, have come into the purview of these new constructive techniques. Underlying these techniques are certain mathematical concepts from differential topology, more specifically degree theory (Brouwer) and homotopies. Usually, the mathematical machinery required for these concepts necessitates a keen familiarity with piecewise linear and/or differential topology.

In this paper, the development is made by following the paths arising from an ordinary differential equation. The differential equation results from Cramer's rule for linear equations. The applicability and ease of our approach are shown by obtaining simple proofs of theorems in differential topology.
Combinatorial Optimization with Rational Objective Functions
Authors: Megiddo Nimrod
Published: October 2008

Let A be the problem of minimizing c1, x1, + ⋯ + cnxn subject to certain constraints on x = (x1, …, xn), and let B be the problem of minimizing (a0 + a1x1 + ⋯ + anxn)/(b0 + b1x1 + ⋯ + bnxn) subject to the same constraints, assuming the denominator is always positive. It is shown that if A is solvable within O[p(n)] comparisons and O[q(n)] additions, then B is solvable in time O[p(n)(q(n) + p(n))]. This applies to most of the “network” algorithms. Consequently, minimum ratio cycles, minimum ratio spanning trees, minimum ratio (simple) paths, maximum ratio weighted matchings, etc., can be computed withing polynomial-time in the number of variables. This improves a result of E. L. Lawler, namely, that a minimum ratio cycle can be computed within a time bound which is polynomial in the number of bits required to specify an instance of the problem. A recent result on minimum ratio spanning trees by R. Chandrasekaran is also improved by the general arguments presented in this paper. Algorithms of time-complexity O(|E| · |V|2 · log|V|) for a minimum ratio cycle and O(|E| · log2|V| · log log |V|) for a minimum ratio spanning tree are developed.
Necessary and Sufficient Conditions for Optimal Search Plans for Moving Targets
Authors: Stone Lawrence D.
Published: October 2008

Let {Xt, t ≥ 0} be a stochastic process representing the motion of a target in Euclidean n-space. Search effort is applied at the rate m(t) > 0 for 0 ≤ t ≤ T, and it is assumed that this effort can be distributed as finely as desired over space. We seek an optimal search plan, i.e., an allocation of effort in time and space which maximizes the probability of detecting the target by time T. When the detection function is concave, theorem 1′ of this paper gives necessary and sufficient conditions for an optimal search plan for a class of target motion processes {Xt, t ≥ 0} which includes virtually any reasonable model of target motion.

In the special case of a discrete-time target motion process and an exponential detection function, the necessary and sufficient conditions have the following intuitive interpretation: For t = 0, 1, 2, …, T, let g̃t, be the probability distribution of the target's location at time t given that the effort at all times before and after t failed to detect the target. The optimal plan allocates the effort for time t so as to maximize the probability of detecting a stationary target with distribution g̃t within the effort constraint m(t). This special case is a generalization of Brown's (Brown, S. S. 1978. Optimal search for a moving target in discrete space and time. Submitted for publication.) result for discrete time and space target motion.
Complexity of Scheduling Shops with No Wait in Process
Authors: Sahni Sartaj , Cho Yookun
Published: October 2008

We show that obtaining minimum finish time schedules with no wait in process is NP-Hard for flow shops, job shops and open shops. Specifically, it is shown that the two processor job and open shop problems are NP-Hard even when jobs are restricted to have no task of length zero. The two processor flow shop problem is NP-Hard if jobs with only one task are permitted. Note that Gilmore and Gomory (Gilmore, P., R. Gomory. 1964. Sequencing a one state-variable machine: A solvable case of the travelling salesman problem. Oper. Res. 12 655–679.) have obtained a polynomial time algorithm for the two processor flow shop for the case where every job has two tasks. The 4-sum and 2-pair problems are also shown NP-Hard.
The Generalized Gradient of a Marginal Function in Mathematical Programming
Authors: Gauvin Jacques
Published: October 2008

We consider the marginal function of a vertically perturbed nonlinear mathematical program with equality and inequality constraints. Conditions are given to have this function locally Lipschitz and to obtain estimates for its generalized gradient.
A Complementary Pivoting Approach to Parametric Nonlinear Programming
Authors: Kojima Masakazu
Published: October 2008

A family of nonlinear programming problems: minimize θ(t, u) subject to g(t, u) ≤ 0 and u ≥ 0 is considered, where t is a scalar parameter changing from 0 to +∞, u an n-dimensional variable vector, θ a continuous real valued mapping defined on the (1 + n)-dimensional space and g a continuous mapping from the (1 + n)-dimensional space into the m-dimensional space. It is assumed that for each fixed t, θ(t, ·) and gj(t, ·) (j = 1, …, m) have partial derivatives ∂θ(t, u)/∂ui and ∂gj(t, u)/∂ui(i = 1, …, n, j = 1, …, m) which are continuous with respect to both t and u. Under a moderate constraint qualification, this paper applies the complementary pivoting theory to the computation of a piecewise linear path in the product space of the parameter t and the variable vector u from which we can approximately know how a Kuhn-Tucker's stationary solution to the problem moves as the parameter t changes from 0 to any given nonnegative number.